Loading
Loading
Two walkers at different speeds reveal cycles and midpoints.
Advance one pointer one step at a time and another two steps at a time. If the structure contains a cycle the fast pointer eventually laps the slow one and they meet; if it does not, the fast pointer runs off the end. The same trick locates the midpoint in a single pass, without first measuring the length.
Relative speed is one step per iteration, so the gap closes by exactly one each time. Inside a cycle of length L, the pointers must therefore meet within L iterations.
The shape, not a solution. Adapt the condition and the state to the problem in front of you.
def has_cycle(head): slow = fast = head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow is fast: return True return False def cycle_start(head): """Floyd's algorithm: detect, then walk to the entry point.""" slow = fast = head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow is fast: # Distance from head to the cycle entry equals the distance # from the meeting point to the entry. Walking both at the same # speed therefore lands them together exactly at the entry. walker = head while walker is not slow: walker = walker.next slow = slow.next return walker return None def middle(head): """When fast reaches the end, slow is at the midpoint.""" slow = fast = head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next return slow| Status | Problem | Difficulty | Role |
|---|---|---|---|
| Middle of the Chain#38 | Easy | Primary | |
| Drop the Nth Stage from the End#40 | Medium | Primary | |
| Does the Chain Loop?#41 | Medium | Primary | |
| Does the Digit Chain Settle?#126 | Easy | Primary |
Sign in to keep a note here. It is free, and nobody else can see it.
Sign in