Lesson 8 of 16 Stacks and Linked Lists

Fast and Slow Pointers (Floyd's Cycle)

Fast and slow pointers: middle of a linked list, Floyd cycle detection, finding where the cycle starts, and find the duplicate number in O(1) space.

30-40 min intermediate 0/16 lessons done
Course contents Lesson 8 of 16 · 0 done
On this page (8 sections)
  1. What you will learn
  2. Signals
  3. Code
  4. Why the reset works
  5. Related
  6. Key takeaways
  7. Exercises
  8. Quiz

What you will learn

  • Using two speeds to find the middle of a list in one pass.
  • Floyd’s cycle detection and why the reset step finds the cycle start.
  • Applying the same idea to arrays (find the duplicate number).

Signals

  • Linked list problems asking for the middle, a cycle, or the k-th node from the end.
  • “O(1) extra space” where a visited set would otherwise be the easy answer.
  • A function x → f(x) iterated repeatedly (happy number, array index jumps): that’s an implicit linked list.

Code

"""Fast and slow pointers on linked lists and implicit sequences."""


class Node:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt


def build(values, cycle_to=None):
    nodes = [Node(v) for v in values]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    if cycle_to is not None:
        nodes[-1].next = nodes[cycle_to]
    return nodes[0]


def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow.val


def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:  # they met inside the cycle
            slow = head   # Floyd: restart one pointer; they meet at the cycle start
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow.val
    return None


def find_duplicate(nums):
    """Array of n+1 values in 1..n: treat i -> nums[i] as a linked list with a cycle."""
    slow = fast = nums[0]
    while True:
        slow, fast = nums[slow], nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]
    while slow != fast:
        slow, fast = nums[slow], nums[fast]
    return slow


if __name__ == "__main__":
    print(middle(build([1, 2, 3, 4, 5])), middle(build([1, 2, 3, 4, 5, 6])))
    print(cycle_start(build([3, 2, 0, -4], cycle_to=1)), cycle_start(build([1, 2, 3])))
    print(find_duplicate([1, 3, 4, 2, 2]), find_duplicate([3, 1, 3, 4, 2]))

Output:

3 4
2 None
2 3
  • Middle: when fast reaches the end, slow is halfway. For even lengths this returns the second middle (4 for six nodes).
  • Cycle start: after slow and fast meet, reset one pointer to the head and move both one step at a time; they meet at the start of the cycle.
  • Find the duplicate: with n+1 values in 1..n, i → nums[i] must form a cycle, and the duplicate value is where the cycle begins. O(n) time, O(1) space, array untouched.

Why the reset works

Let the distance from the head to the cycle start be a, and the meeting point be b steps into the cycle of length c. Slow travelled a + b, fast travelled twice that, and the difference is a whole number of loops: a + b = m·c. So a = m·c - b: walking a steps from the meeting point lands exactly on the cycle start, the same place a pointer walking a steps from the head arrives.

  • k-th node from the end: move one pointer k steps ahead, then move both until the leader hits the end.
  • Palindrome linked list: find the middle, reverse the second half, compare.
  • Happy number: iterate digit-square sums; a cycle not containing 1 means unhappy.

Practise: fast & slow pointer problems and general linked list problems.

Key takeaways

  • Two pointers at speeds 1 and 2 find middles and cycles in one pass with O(1) space.
  • After meeting, reset one pointer to the head; stepping both by one meets at the cycle start.
  • Any repeated function application is an implicit linked list.

Exercises

  1. Remove the k-th node from the end of a list in one pass.
  2. Check whether a linked list is a palindrome in O(1) extra space.
  3. Implement “happy number” with fast and slow pointers.

Quiz

  1. For a six-node list, which middle does middle() return?
  2. Why must a cycle exist in find-the-duplicate?
  3. After slow and fast meet, why do head-reset steps find the cycle start?
Show answers
  1. The second middle (the 4th node, value 4).
  2. There are n+1 indices but only n possible values, so following i → nums[i] must eventually revisit a value (pigeonhole).
  3. Because a = m·c - b: the distance from head to the start equals the distance from the meeting point forward to the start, modulo full loops.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).