Middle of the Linked List — Fast and Slow Pointers

Problem 207 · Middle of the Linked List

Difficulty: Easy · Pattern: Fast/Slow Pointers

Return the middle node; if two middles, return the second.

Solutions

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

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

# Python
def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Complexity

Time: O(n)
Space: O(1)

Why It Works

Fast moves 2× speed, so when fast reaches the end, slow is at n/2.