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
fastreaches the end,slowis halfway. For even lengths this returns the second middle (4 for six nodes). - Cycle start: after
slowandfastmeet, 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.
Related
- 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
- Remove the k-th node from the end of a list in one pass.
- Check whether a linked list is a palindrome in O(1) extra space.
- Implement “happy number” with fast and slow pointers.
Quiz
- For a six-node list, which middle does
middle()return? - Why must a cycle exist in find-the-duplicate?
- After slow and fast meet, why do head-reset steps find the cycle start?
Show answers
- The second middle (the 4th node, value 4).
- There are n+1 indices but only n possible values, so following
i → nums[i]must eventually revisit a value (pigeonhole). - 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.