Fast & Slow PointersFast and slow pointers

01Why it exists

Reach for it when you see:Whether there is a cycle, where a cycle starts, the middle node, the kth node from the end, only one pass allowed, no extra space allowed, two pointers moving at different speeds.

02The core idea

The fast and slow pointer technique runs two pointers along the same list at different speeds, or from different starting points, and answers questions from the distance relationship between them. The slow pointer takes one step at a time and the fast one takes two, so fast always covers twice the distance slow does — which means that when fast reaches the end, slow is at the middle.

Cycle detection works on the intuition of a chase. If there is a cycle, fast enters it and keeps going round; once slow enters too, fast closes the gap by 1 each round and catches up within at most one lap. If there is no cycle, fast hits None first. The whole thing uses two pointers, O(n) time and O(1) space.

Finding where the cycle starts adds one more phase. Let a be the distance from head to the start of the cycle and c the cycle's length. At the meeting point slow has walked a + b and fast has walked 2(a + b), so the difference is a whole number of laps, which gives a ≡ −b (mod c). In other words, walking another a steps from the meeting point lands you exactly on the start of the cycle. So put one pointer back at head, leave the other where they met, move both one step at a time, and where they meet again is the start.

The same family includes the fixed gap trick: send fast k steps ahead, then move both at the same speed, and when fast reaches the end slow sits on the kth node from the end. In every case, the point is to maintain a known relationship between the two pointers.

03The algorithm

1. 1slow = fast = head. The loop condition is always while fast and fast.next, which is what keeps fast.next.next from blowing up.
2. 2Each round: slow = slow.next and fast = fast.next.next.
3. 3Finding the middle: return slow once the loop ends. On an even-length list it stops at the second middle node; start fast from head.next if you want the first one instead.
4. 4Detecting a cycle: check slow is fast after moving them each round. Compare after the move, since the two start out equal by definition.
5. 5The start of the cycle: once they meet, set slow = head and move both one step at a time until they meet again. The kth node from the end: send fast k steps ahead, then move both at the same speed.

04Interactive demo

"Find the middle" shows where slow ends up when fast runs off the end. "Detect a cycle" shows how the two pointers meet inside the loop, and how the second phase locates the node where the cycle begins.

05Code

Four functions built on one skeleton: the middle node, cycle detection, the start of the cycle, and the kth node from the end. Notice that the loop condition is identical in all of them — only when they stop, and what they do afterwards, differs.

# Find the middle: fast moves two steps, slow moves one, so slow is halfway when fast runs out
def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow            # on an even-length list this is the second middle node


# Cycle detection (Floyd): if there is a cycle, fast is bound to catch slow
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


# Find where the cycle starts: after they meet, send one pointer back to head and step both one at a time
def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None


# The kth node from the end: fast goes k steps ahead, then both move until fast runs out
def kth_from_end(head, k):
    slow = fast = head
    for _ in range(k):
        fast = fast.next
    while fast:
        slow = slow.next
        fast = fast.next
    return slow

06Practice

• LeetCode 876Middle of the Linked ListEasy
• LeetCode 141Linked List CycleEasy
• LeetCode 142Linked List Cycle II (where the cycle starts)Medium
• LeetCode 19Remove Nth Node From End of List (a fixed gap)Medium
• LeetCode 287Find the Duplicate Number (treat the array as a list and find the cycle)Medium
• LeetCode 143Reorder List (middle, reverse, then interleave)Medium