Linked List Cycle

Easy#141cycle

You get the head of a linked list. The last node may point back to some earlier node instead of to none, and then walking the list never ends. Return true if the list loops like that and false if it ends. Our example: 4 → 9 → 1 → 7 → 3 → 8 → 6, and 6 points back to 1 — the answer is true.

141 Linked List CycleWalkthrough · 1×

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

head4917386slow
slowfastwhere they meet

slow = head, node 4

01/23
restart · back · play · step
Speed
1function hasCycle(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 return true
9 return false
state
slow
4
fast
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. If the list ends, fast gets to none first and the loop stops: false. The check of fast and fast.next comes first, so fast.next.next is never taken from none.
  2. If the list loops, both pointers end up going round the loop. Each round fast walks two steps and slow one, so the gap between them shrinks by exactly one: fast cannot jump over slow, it lands on it.
  3. «slow is fast» compares nodes, not values: two different nodes may hold the same number.

Complexity

Time O(n): fast catches slow before slow has gone once round the loop, so slow takes fewer than n steps and fast fewer than 2n. Memory O(1): two pointers and 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.