106. Find Cycle Entry

Why this mechanism works

First find a slow/fast meeting. If the noncyclic prefix length is mu and cycle length is lambda, the meeting relation implies mu plus the meeting's cycle offset is a multiple of lambda. Moving one pointer from head and one from the meeting at equal speed therefore makes them meet at the entry.

State and boundaries

The first phase locates any meeting in the cycle. In the second, entry starts at head while slow remains at the meeting; both move one link per step.

Protocol

1. Run guarded slow/fast movement until meeting or exhaustion.
2. Return None if there is no meeting.
3. Reset one pointer to head.
4. Advance both one step until identities match.
5. Return that node.

Visualization

head -- mu links --> entry -- cycle offset --> meeting
meeting pointer + mu steps wraps to entry
head pointer + mu steps reaches entry

Python implementation

from structures import build_list

def cycle_entry(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:
            break
    else:
        return None
    entry = head
    while entry is not slow:
        entry = entry.next
        slow = slow.next
    return entry

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 cycle_entry: slow = fast = head
head=N1(val=7,next=N2,random=None); slow=N1(val=7,next=N2,random=None); fast=N1(val=7,next=N2,random=None)

L6 cycle_entry: slow = slow.next
head=N1(val=7,next=N2,random=None); slow=N2(val=7,next=N3,random=None); fast=N1(val=7,next=N2,random=None)

L7 cycle_entry: fast = fast.next.next
head=N1(val=7,next=N2,random=None); slow=N2(val=7,next=N3,random=None); fast=N3(val=7,next=N2,random=None)

L6 cycle_entry: slow = slow.next
head=N1(val=7,next=N2,random=None); slow=N3(val=7,next=N2,random=None); fast=N3(val=7,next=N2,random=None)

L12 cycle_entry: entry = head
head=N1(val=7,next=N2,random=None); slow=N3(val=7,next=N2,random=None); fast=N3(val=7,next=N2,random=None); entry=N1(val=7,next=N2,random=None)

L14 cycle_entry: entry = entry.next
head=N1(val=7,next=N2,random=None); slow=N3(val=7,next=N2,random=None); fast=N3(val=7,next=N2,random=None); entry=N2(val=7,next=N3,random=None)

L15 cycle_entry: slow = slow.next
head=N1(val=7,next=N2,random=None); slow=N2(val=7,next=N3,random=None); fast=N3(val=7,next=N2,random=None); entry=N2(val=7,next=N3,random=None)

L4 cycle_entry: slow = fast = head
head=N1(val=1,next=N2,random=None); slow=N1(val=1,next=N2,random=None); fast=N1(val=1,next=N2,random=None)

L6 cycle_entry: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=None,random=None); fast=N1(val=1,next=N2,random=None)

L7 cycle_entry: fast = fast.next.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=None,random=None); fast=None

Why the solution is correct

At the first meeting, the fast-minus-slow distance is a multiple of the cycle length, yielding the modular relation for the entry offset. After mu equal-speed steps, the head pointer reaches the entry and the meeting pointer reaches the same cycle position. Before then, the head pointer is outside the cycle, so this is their first match.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Resetting both pointers to head loses the needed meeting offset. Returning the first meeting node is not generally returning the cycle entry.

Reasoning card

Transfer exercise

Derive an alternative entry search using the measured cycle length as a fixed gap between two pointers.