Find the Cycle Start
Linked Lists: lesson 7 of 10
Knowing a loop exists is half the job — now find its door.
Lesson 7 of 10 · 6 min
Find the Cycle Start
Step 1 of 8
Node 5 links back to node 2, so the chain has no end. Both walkers start on the head.
The Idea
Once slow and fast collide you know there is a loop, but not where it begins. Here is the trick: move one walker back to the head and let both step one node at a time. They meet exactly at the entry.
Why? The distance from the head to the entry equals the distance from the meeting point back round to the entry. Both walkers cover the same gap.
Real-World Example
Two runners on a lollipop-shaped course discover they have lapped each other. Send one back to the start line and let them jog at the same pace — they rejoin at the junction where the straight meets the loop, every time.
The Code
class Node:
def __init__(self, v): self.val, self.next = v, None
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast: # met somewhere inside the loop
slow = head # restart one walker at the head
while slow is not fast: # both take single steps from here
slow, fast = slow.next, fast.next
return slow.val # they meet again at the entry
return None
n = [Node(i) for i in range(6)]
for a, b in zip(n, n[1:]): a.next = b # 0 -> 1 -> 2 -> 3 -> 4 -> 5
n[5].next = n[2] # ...and 5 links back to 2
print(cycle_start(n[0])) # 2Your turn
What does this print?
class Node:
def __init__(self, v): self.val, self.next = v, None
n = [Node(i) for i in range(5)]
for a, b in zip(n, n[1:]): a.next = b
n[4].next = n[1]
slow = fast = n[0]
while True:
slow, fast = slow.next, fast.next.next
if slow is fast: break
slow = n[0]
while slow is not fast:
slow, fast = slow.next, fast.next
print(slow.val)Mini quiz
1 / 3