Fast & slow pointers

O(n)

Walk two pointers from the head of a list, slow one step and fast two steps at a time. If there is a cycle they must eventually meet; if there is no cycle, fast reaches the end first. The meeting point also finds the middle node.

Signals

detect a cycle in a linked listfind where a cycle beginsfind the middle node of a listdetermine if a list is a palindromeno extra memory / O(1) space, only pointers

Template

function hasCycle(head) {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

Looks similar, isn't

Two pointers (opposite ends): Opposite pointers start at both ends of an array and converge inward. Fast/slow both start at the head of a list and move forward at different speeds; there is no 'other end' to converge from on a singly linked list.

n up to 1e5 nodes -> O(n): fast covers at most 2n steps before meeting slow or reaching null.

Learn this pattern