Middle of a list: fast and slow

Find the middle node in one pass with two references moving at different speeds.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

fast moves two nodes for every one that slow moves. When fast reaches the end, slow has covered exactly half the distance.

Code

C++PythonC#

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

def middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

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

Tips

With an even number of nodes this returns the second of the two middle nodes.
The same two-speed idea detects cycles and finds the k-th node from the end.

In the .NET library

The condition order matters: fast != null is checked first, so fast.next never throws NullReferenceException.