The problem
Given a linked list, decide whether it has a cycle: does following next pointers ever loop back to an earlier node?
Input: 3 → 2 → 0 → −4, and the last node links back to position 1 Output: true
Picture it
Picture a tortoise and a hare on the track. The tortoise moves one coach at a time, the hare two. If the track simply ends, the hare falls off the end: no cycle. If the track loops, the hare laps around and must eventually land on the same coach as the tortoise.
How to recognise it
- You follow "next" links and need to know whether the walk ever comes back to a node it has visited.
- If there is no cycle, the walk ends at
None. If there is one, it goes round forever, so a plain walk cannot tell "very long" from "endless". - The follow-up asks for O(1) memory, which rules out remembering visited nodes.
- The same "fast and slow pointer" trick (Floyd's cycle detection) works on anything that maps a state to one next state: Happy Number, Find the Duplicate Number, random-number generators.
Start with brute force
Remember every node you have visited in a set. If you reach a node that is already in the set, the list loops.
def has_cycle_brute(head):
seen = set()
node = head
while node:
if node in seen:
return True
seen.add(node)
node = node.next
return False
Python hashes plain objects by identity, so two nodes with the same value are still different keys. Time is O(n) and space is O(n). With LeetCode's 10^4 nodes it is fast; the cost is the set of up to 10^4 references, which the follow-up asks you to avoid.
From brute force to the idea
- Find the waste. The set stores every node only to notice one repeat. You do not need to know where the loop is, only whether there is one.
- Race two pointers.
slowmoves one node per step andfastmoves two. Both start at the head. - No cycle: fast falls off. If the list ends,
fastorfast.nextbecomesNonefirst, the loop condition fails, and the answer isFalse. - A cycle: fast catches up. Once both are inside the loop,
fastgains exactly one node per step onslow. The gap shrinks by one each time, so it reaches zero within one lap, and they land on the same node. It can never jump overslow, because it closes the gap one node at a time. - Compare identity.
slow is fastasks "the same node?", not "the same value?".
This is the key idea: a pointer moving twice as fast must either reach the end or lap the slow one.
The key idea
Floyd’s fast/slow pointers: they meet if and only if there is a cycle. O(n) time, O(1) space.
Python solution
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n): each node is visited and added to the set once | O(n): the set of visited nodes |
| Fast and slow (shown code) | O(n): slow enters the loop within n steps, then they meet within one more lap | O(1): two references |
Edge cases
- Empty list:
fastisNone, the loop is skipped, and the code returnsFalse. - One node, no cycle:
fast.nextisNone, so it returnsFalse. - One node pointing to itself: after one step both pointers are back on that node, so it returns
True. - Two nodes pointing at each other: returns
True. - Cycle that starts late (
3 → 2 → 0 → −4, with −4 linking back to 2): returnsTrue. They meet somewhere in the loop, not necessarily at its start. - Repeated values without a cycle (
1 → 1 → 1): returnsFalse, because nodes are compared withis, not by value.
Common mistakes
- Comparing
slow.val == fast.val. A list like1 → 1 → 1would be reported as a cycle. - Checking
slow is fastbefore moving the pointers. They both start at the head, so the check succeeds at once. - Looping
while fast.next and fast.next.nextwithout checkingfast: on an empty listfast.nextraisesAttributeError. - Moving
fastthree steps at a time "to be quicker". It still works, but it is no faster in big-O and makes the meeting point harder to reason about.
Return the node where the cycle begins, or None if there is no cycle. For 3 → 2 → 0 → −4 with −4 linking back to 2, return the node holding 2. Use O(1) memory. Describe your approach, then write it if you like.
Compare with our answer
First find a meeting point exactly as before. Then move one pointer back to the head and advance both one step at a time: they meet again at the cycle's start. The reason: if the start is a steps from the head, the meeting point is also a steps (plus some whole laps) before the start, going round the loop.
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow, fast = slow.next, fast.next
return slow
return None
Time O(n), space O(1).
A strong answer mentions: the first meeting only proves a cycle, resetting one pointer to the head, both moving at the same speed in phase two, and the distance argument for why they meet at the start.
1. Repeatedly replace a number by the sum of the squares of its digits. Decide whether it ever reaches 1, using O(1) memory. Which approach fits best?
Each number has exactly one "next" number, like a linked list, so Floyd's fast and slow walk detects the loop in O(1) memory. A set works but uses memory, and a fixed step limit is a guess.
2. Why are the fast and slow pointers guaranteed to meet when there is a cycle?
fast gains one node per step, so the gap goes n, n − 1, …, 0 and cannot skip zero. Cycles can have any length, and neither pointer stops or restarts.
3. A learner moves if slow is fast: return True to the top of the loop, before the pointers move. What happens?
Both pointers start at the head, so on the first pass slow is fast is already true. Only an empty or one-node list skips the loop and returns False.
Score 60% or more and the lesson is marked complete.