Middle of the Linked List

Return the middle node (the second middle for even lengths). Move slow one step and fast two steps; when fast reaches the end, slow is in the middle.

Traced input: head = [1, 2, 3, 4, 5, 6] → [4, 5, 6]. Original problem: neetcode.io/problems/middle-of-the-linked-list

Complexity

fast walks the list once.

Key idea

• fast covers twice the distance, so slow is halfway when fast finishes.
• Loop while fast != null && fast.next != null.
• For even lengths this lands on the second middle, which the problem wants.

Common mistakes

• Looping on fast.next.next != null returns the first middle instead.
• Counting the length first works but takes two passes.

Solution

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

def middleNode(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Edge cases

Each one has its own trace in the interactive view.