Linked List Cycle II

Medium#142cycle

You get the head of a linked list. If its last node points back to an earlier node, the list loops: return the node where the loop starts, the first one you come to twice. If the list ends in none, return none. Our example: 2 → 6 → 9 → 5 → 1 → 8 → 3, and 3 points back to 5 — the answer is the node 5, index 3.

142 Linked List Cycle IIWalkthrough · 1×

Example: the list 2 → 6 → 9 → 5 → 1 → 8 → 3, where 3 points back to 5.

head2695183slow
slowfastwhere they meet

slow = head, node 2

01/30
restart · back · play · step
Speed
1function detectCycle(head):
2 slow = head
3 fast = head
4 while fast and fast.next are not none:
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
state
slow
2
fast
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Let a be the steps from the head to the loop's start and L the loop's length. When they meet, fast has walked twice as far as slow, and the extra distance is whole laps: slow has walked a multiple of L.
  2. So from the meeting point, a more steps bring slow to a + (a multiple of L), which is the loop's start. A pointer from the head reaches the start in the same a steps.
  3. Both move one step at a time in the second loop, so they first share a node exactly at the start, never earlier: before it one is still on the tail and the other on the loop.

Complexity

Time O(n): the first loop takes fewer than n rounds, as in Linked List Cycle, and the second exactly a, the length of the tail. Memory O(1): two pointers, no set of visited nodes.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.