Drag across the track. Click it, then use ← → to step and Space to play.
Two pointers walk the same linked list at different speeds: slow moves one node per turn, fast moves two. If there is a cycle, fast eventually laps slow and they land on the same node; if there isn't, fast reaches the end, and at that moment slow is exactly halfway. No visited set, no length count: O(n) time and O(1) space.
FIG. 15 · The list drawn on the board from page 6, one-way grooves pointing to next. The black marble S is slow, the red marble F is fast; their gates are ringed in the same colours, and a gate turns solid red when both stand on it. The grooves just travelled light up. Callout: A head.
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 False
def middle(head): # second middle if even length
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def detectCycle(head): # LeetCode 142
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # phase 1: they meet inside the cycle
slow = head # phase 2: one restarts from head
while slow is not fast:
slow = slow.next # both now move one step
fast = fast.next
return slow # where they meet = cycle start
return None
def findDuplicate(nums): # LeetCode 287
slow = fast = 0 # index i points to nums[i]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = 0 # phase 2: find the cycle entrance
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Not just "is there a cycle" but "where does it start". After the pointers meet, move one back to the head and walk both one step at a time; they meet again exactly at the start of the cycle. Answer: node 4.
nums = [1, 3, 4, 2, 2]. Read index i as a node pointing to nums[i]. The repeated value has two arrows into it, so following the arrows must loop, and the loop's entrance is the duplicate. Answer: 2, without modifying the array or using extra memory. Trigger: "find the duplicate number".
| Approach | Time | Space | Why |
|---|---|---|---|
| Fast and slow pointers | O(n) | O(1) | Once both are on the loop, the gap closes by one node per turn, so they meet within one lap. |
| Visited set (page 9) | O(n) | O(n) | Remember every node; the first repeat is the cycle. Simpler, but costs memory. |
| Middle by counting | O(n) | O(1) | Two passes (count, then walk n/2). Fast and slow do it in one. |
Once both pointers are inside the loop, look at the gap from slow forward to fast. Each turn slow adds 1 and fast adds 2, so the gap shrinks by exactly 1. A gap that shrinks by 1 each turn hits 0; it can never jump over it. That's also why fast moves 2 and not 3: with 3 it could skip past slow.
Say the tail before the loop has length a and they met b steps into the loop of length c. Slow walked a + b, fast walked twice that, and the extra a + b is a whole number of laps. So a ≡ c − b (mod c): walking a more steps from the meeting point lands on the loop's start, exactly where a pointer from the head arrives after a steps.
Two speeds on one list, no extra memory.
Any "next" function (i → nums[i], n → sum of digit squares) forms a list you can race on.
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 False
def middle(head): # second middle if even length
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow