Linked List Cycle II - Floyd Explained Visually

Why it works

Inside a loop, a faster runner must eventually lap a slower one - meeting is proof of a cycle, no extra memory needed. The second phase works because the distance from head to entry equals the distance from the meeting point to entry, modulo the cycle length.

The problem

Given a linked list, return the node where the cycle begins. If there is no cycle, return None. Floyd's algorithm can detect the cycle AND find the entry point.

Hints

• Phase 1: use slow (1 step) and fast (2 steps). If they meet, a cycle exists.
• Phase 2: when they meet, reset one pointer to head.
• Advance both one step at a time - they'll meet at the cycle entry.
• Mathematical proof: distance from head to entry == distance from meeting point to entry.

Test cases

Reference starter code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detect_cycle(head):
    # Phase 1: detect cycle with slow/fast pointers
    # Phase 2: find entry point
    pass

# Build a list with cycle for testing
def make_cycle_list(vals, pos):
    nodes = [ListNode(v) for v in vals]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if pos >= 0:
        nodes[-1].next = nodes[pos]
    return nodes[0] if nodes else None

head = make_cycle_list([3, 2, 0, -4], 1)
result = detect_cycle(head)
print(result.val if result else None)  # 2 (cycle at index 1)

head2 = make_cycle_list([1, 2], -1)
print(detect_cycle(head2))  # None

More challenges in this topic

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.