LeetCode #142 Medium

Linked List Cycle II

Given a linked list, return the node where the cycle begins — not just whether one exists. Return null if there is no cycle. O(1) memory required.

linked listtwo pointersfloyd

Open on LeetCode ↗

02

Intuition

Run the slow/fast race until they meet inside the loop. Then the magic: reset one pointer to the head and walk both one step at a time — they collide exactly at the cycle's entrance. The distances cancel out perfectly.

How to spot this pattern

The follow-up with a genuinely surprising result: after the pointers meet, reset one to the head and advance both one step at a time — they meet again exactly at the cycle's entrance. It falls out of the algebra (the distance from head to entry equals the distance from the meeting point to entry, modulo the loop length), and it's worth being able to state that rather than just memorising the move.

03

Approach

1

Phase 1 — detect with slow/fast

Same as Cycle I: slow moves 1, fast moves 2. If fast falls off the end there's no cycle → null. If they meet, a cycle exists and the meeting point is somewhere inside it.

2

Phase 2 — the distance cancellation

Call the head→entry distance a, entry→meeting b, and the cycle length c. When they meet, fast has walked exactly twice slow's distance: a + b + kc = 2(a + b), which simplifies to a = c − b (mod c). Translation: from the meeting point, the entry is exactly a steps ahead — the same distance as from the head.

3

Walk both ×1 and collide at the entry

So reset slow to the head, keep fast at the meeting point, and advance both one step at a time. After a steps they are both standing on the cycle's first node — return it. No counting, no hashing, O(1) space.

04

Solution & live demo

▶1class Solution:
▶2    def detectCycle(self, head):
▶3        slow = fast = head
▶4        while fast and fast.next:
▶5            slow = slow.next
▶6            fast = fast.next.next
▶7            if slow is fast:
▶8                slow = head
▶9                while slow is not fast:
▶10                    slow = slow.next
▶11                    fast = fast.next
▶12                return slow
▶13        return None

05

Common pitfalls

Returning the meeting point as the entrance

✗ Wrong

if slow is fast:
    return slow

✓ Right

if slow is fast:
    slow = head
    while slow is not fast:
        slow = slow.next; fast = fast.next
    return slow

The meeting point is wherever the lap happened to complete, which is generally somewhere in the middle of the cycle rather than its entrance. The second phase is what converts one into the other.

Keeping the fast pointer at double speed in phase two

✗ Wrong

while slow is not fast:
    slow = slow.next
    fast = fast.next.next

✓ Right

while slow is not fast:
    slow = slow.next
    fast = fast.next

The equal-distance argument only holds at matched speed. Leaving the hare at double pace makes the two pointers meet somewhere arbitrary inside the loop, or miss the entrance entirely.

Resetting the wrong pointer

✗ Wrong

fast = head

✓ Right

slow = head

Either works as long as the other stays at the meeting point — but resetting both, or resetting one and then advancing from the wrong start, breaks the invariant. Exactly one pointer returns to the head.

06

Edge cases

No cycle

Fast (or fast.next) hits null in phase 1 — return null before phase 2 ever runs.

Cycle starts at the head

a = 0: phase 2's loop condition is false immediately and the head itself is returned.

Whole list is one small loop

The meeting can happen anywhere in the loop; the cancellation argument doesn't care — phase 2 still lands on the entry.

07

Complexity

Time

O(n)

Space

O(1)

Phase 1 is at most 2n steps; phase 2 at most n more. Two pointers, no extra memory.