Middle of the Linked List

Problem Statement

LeetCode-876: Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Approach

The problem can be solved using the slow and fast pointer approach. The slow pointer moves one step at a time, and the fast pointer moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle of the list.

Implementation

Following is the implementation of the above approach.

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while(null != fast){
        fast = fast.next;
        if(null != fast){
            fast = fast.next;
            slow = slow.next;
        }
    }
    return slow;
}

Complexity Analysis

The time complexity for the above approach is $O(n)$, where $n$ is the number of nodes in the linked list.