LeetCode 876: Middle of the Linked List

Explanation

To find the middle node of a linked list, we can use the two-pointer approach. We will use two pointers, a slow pointer and a fast pointer. The slow pointer moves one step at a time while 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 node.

Algorithm:

1. Initialize two pointers, slow and fast, pointing to the head of the linked list.
2. Move slow pointer one step and fast pointer two steps at a time until the fast pointer reaches the end of the list.
3. Return the node pointed by the slow pointer, which will be the middle node.

Time Complexity: O(N) where N is the number of nodes in the linked list. Space Complexity: O(1)

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}