Fast and slow pointers and merging lists

Two pointers on a linked list

Module 3 used two pointers on arrays. On a linked list you cannot jump to an index, but you can walk two pointers at different speeds, or keep a fixed gap between them. That answers questions about the middle, cycles and the end of the list in one pass, with O(1) extra space.

The middle of a list

Move slow one step and fast two steps at a time. When fast reaches the end, slow has gone half as far, so it is at the middle. With the loop condition while fast and fast.next, an even-length list gives the SECOND of its two middle nodes: for 1 → 2 → 3 → 4 it stops at 3. Write while fast.next and fast.next.next instead to stop at the first middle, 2; that version is used to split a list in half for merge sort.

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
# 1 -> 2 -> 3 -> 4 -> 5   gives the node 3
# 1 -> 2 -> 3 -> 4        gives the node 3 (the second middle)

Detecting a cycle: Floyd's tortoise and hare

A cycle means some node's next points back to an earlier node, so walking never reaches None. A plain loop like while node: node = node.next then runs forever. One fix is a set of visited nodes, which costs O(n) extra space. Floyd's algorithm uses O(1): move slow one step and fast two steps. Without a cycle, fast reaches the end. With a cycle, both pointers end up inside it, and each step fast gains exactly one node on slow, so the gap shrinks to zero and they meet.

Compare nodes with slow is fast, not their values: two different nodes can hold the same value.

Where the cycle starts

After slow and fast meet, put one pointer back at the head and move both ONE step at a time. They meet again exactly at the first node of the cycle. Why: let a be the distance from the head to the cycle start, b the distance from the start to the meeting point, and c the cycle length. Fast walked twice as far as slow: 2(a + b) = a + b + k·c for some whole number of laps k, so a = k·c − b. Walking a steps from the meeting point therefore lands on the cycle start, which is also where a pointer from the head arrives after a steps.

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:              # they met inside the cycle
            p = head
            while p is not slow:
                p = p.next
                slow = slow.next
            return p                  # first node of the cycle
    return None                       # fast reached the end: no cycle

The n-th node from the end

To remove the n-th node from the end in one pass, keep a gap of n nodes between two pointers. Start both at a dummy node before the head and move fast n + 1 steps ahead. Then move both one step at a time until fast is None. Now slow sits just BEFORE the node to remove, so slow.next = slow.next.next deletes it. The dummy covers the case where the head itself is removed (n equal to the length).

Merging two sorted lists with a dummy node

The array merge from Module 3 works on lists too, without copying values: relink the existing nodes. A dummy node gives the merged list a fixed start, and a tail pointer marks where the next node goes. When one list runs out, attach the rest of the other in one step, because it is already sorted. O(n + m) time and O(1) extra space.

dummy = tail = ListNode()
while a and b:
    if a.val <= b.val:
        tail.next, a = a, a.next
    else:
        tail.next, b = b, b.next
    tail = tail.next
tail.next = a or b          # attach whatever is left
merged = dummy.next

Palindrome linked list

Is 1 → 2 → 2 → 1 the same backwards? Copying the values into a Python list and comparing it with its reverse works in O(n) time but uses O(n) extra space. The O(1)-space way combines this module's tools: find the middle with slow and fast pointers, reverse the second half (Topic 4), then walk from the head and from the reversed half together, comparing values. Reverse the second half back afterwards if the caller still needs the list.

Common mistakes

• Writing while fast.next and fast, which crashes when fast is None. Fix: while fast and fast.next (check fast first).
• Comparing values instead of nodes when looking for a cycle. Fix: slow is fast.
• An off-by-one gap in n-th from the end. Fix: start at a dummy and move fast n + 1 steps.
• Forgetting to attach the leftover part after merging. Fix: tail.next = a or b.
• Not saying which middle you return for even lengths. Fix: state it, then choose the loop condition to match.
• Printing or converting a list that may have a cycle, which never ends. Fix: detect the cycle first.