Find the duplicate number
StopLinked list
- CH1 slow
- CH2 fast
16/16
Each value links to an index. Where the loop starts, two links meet: that index is the duplicate.
Step through it →Fast & Slow Pointers
Two pointers follow the same links, one twice as fast. If the links loop, the fast one catches the slow one; if not, it reaches the end first.
Linked list cycle: does the list loop back?
StopLinked list
valuespos
- CH1 slow
- CH2 fast
slow and fast both start at the head, 3.
Typical cost O(n) time, O(1) spaceFull lesson: Linked List Cycle →
When to reach for it
- You need to know whether following next ever repeats.
- You're allowed O(1) extra space, so no visited set.
- An array's values point at its own indices, as in Find the Duplicate Number.
- You want the middle of a list in one pass.
What stays true
Each step moves slow one link and fast two. Once both are in the loop, fast gains exactly one link a step, so it can't jump over slow. It lands on slow within one lap.
fast has gone twice as far
StopLinked list
Invariantfast has always gone twice as many links as slow.✓ Holds
- CH1 slow
- CH2 fast
slow and fast both start at the head, 1.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
Comparing slow and fast before moving them says True at once, since both start at the head. And checking only fast before fast.next.next crashes on the last node.
Linked list cycle on the inputs that trip it up
StopLinked list
- CH1 slow
- CH2 fast
slow and fast both start at the head, 1.
AnswerfalseSteps6
Variants
The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Linked list cycle: does the list loop back?
StopLinked list
- CH1 slow
- CH2 fast
slow and fast both start at the head, 3.
linked_list_cycle.py
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 FalseDrill it
Linked List CycleRuns live,EasyFind the Duplicate NumberRuns live,Medium
Middle of the Linked ListEasy
Happy NumberEasy