Linked List Cycle
Picture
Slow moves one edge; fast moves two. On an acyclic chain, fast reaches the end first.
Predict
Does the first slow-fast meeting always equal the cycle entrance?
Walk through the small example
No. Different speeds guarantee a meeting in a finite cycle; equal-speed phase two locates its entrance.
Mental model and complete Python solution
Fast’s extra distance at the meeting is a whole number of cycle lengths. That congruence makes distance from head to entrance match the remaining cycle distance from meeting.
What the function promises: Return the entrance node of a stable singly linked list cycle, or None.
class Node:
def __init__(self, value, next_node=None):
self.value, self.next = value, next_node
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
answer = []
while head is not None:
answer.append(head.value)
head = head.next
return answer
def cycle_entrance(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow, fast = slow.next, fast.next.next
if slow is fast:
seeker = head
while seeker is not slow:
seeker, slow = seeker.next, slow.next
return seeker
return None
a, b, c = Node(1), Node(2), Node(3)
a.next, b.next, c.next = b, c, b
assert cycle_entrance(a) is b
assert cycle_entrance(build([1,2])) is None
Work and storage: O(n) time and O(1) extra space.
When to recognize it: Different speeds guarantee a meeting in a finite cycle; equal-speed phase two locates its entrance.
Check before applying it: The arithmetic assumes deterministic next references that do not change during traversal.
Change one rule
Need the cycle length too.
See what changes
After the meeting, walk once around the cycle while counting edges.
Connect
Linked lists: follow references: The graph has outdegree at most one.
components coloring: General graph cycles need broader visited-state reasoning.