You are given the head of a linked list. Return true if the list has a cycle, and false otherwise. A list has a cycle when following next pointers over and over eventually brings you back to a node you have already visited, so the walk never ends.
3 → 2 → 0 → -4 ↑ | └─────────┘ → true (-4 points back to 2)1 → 2 → null → false (the walk reaches the end)
The list has up to 10,000 nodes. The follow-up asks for O(1) extra memory.
If the list has no cycle, walking it eventually reaches null. If it has a cycle, the walk goes round the loop forever. You cannot just walk and wait, because you would never know whether the end is near or whether you are going round in circles.
So the real question is: how do you notice that you have come back to a node you visited before?
Remember every node you have visited, in a set. If you reach a node that is already in the set, you have gone round a loop.
python
def hasCycle(head): seen = set() node = head while node: if node in seen: # back to a node we have visited return True seen.add(node) node = node.next return False # reached the end
This is O(n) time and correct. It is a perfectly good first answer.
The cost in one sentence: it stores every node in a set, which is O(n) memory, when two moving pointers can detect the loop with no memory at all.
Use two pointers that move at different speeds. This is Floyd's cycle detection, often called the tortoise and the hare.
slow moves one node per step.
fast moves two nodes per step.
If there is no cycle, fast reaches the end of the list and we are done. If there is a cycle, both pointers end up going round the loop. Then fast must eventually land on the same node as slow.
Think of two runners on a circular track, one running twice as fast as the other. The fast runner will eventually come up behind the slow one and draw level.
Once both pointers are inside the loop, look at the gap: how many steps fast would need to walk forward round the loop to reach slow.
On every step, slow moves forward 1 and fast moves forward 2. So fast gains exactly 1 step on slow. The gap gets smaller by exactly one each step.
A number that goes down by exactly 1 each time, starting from some whole number, must eventually hit 0. When the gap is 0, the two pointers are on the same node.
The step size of 1 is what makes this certain. Suppose fast moved three nodes per step. Then it would gain 2 per step, and the gap would shrink by 2 each time. If the gap were odd, it would go 3, 1, −1, jumping straight past 0. The pointers could pass each other without ever landing on the same node. Gaining exactly one per step means no number is ever skipped.
That is the whole proof, and it is short enough to say out loud in an interview.
class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow = fast = head # (1) while fast and fast.next: # (2) slow = slow.next # (3) fast = fast.next.next # (4) if slow is fast: # (5) return True return False # (6)
ts
function hasCycle(head: ListNode | null): boolean { let slow = head, fast = head; // (1) while (fast && fast.next) { // (2) slow = slow!.next; // (3) fast = fast.next.next; // (4) if (slow === fast) return true; // (5) } return false; // (6)}
(2) Can fast take two more steps?fast is about to step onto fast.next and then fast.next.next. So both fast and fast.next must exist. Checking only fast would crash when fast.next is None. If either is missing, the list has an end, so there is no cycle.
(3) slow moves one step.
(4) fast moves two steps.
(5) Are they on the same node? We compare identity: is in Python and === in TypeScript, which ask "is this the very same node object?" We do not compare values, because two different nodes can hold the same value.
We check after moving. Both pointers start on the head, so checking before moving would report a cycle at once on every list.
(6) fast reached the end, so the list has no cycle.
Time. Before the loop is reached, slow takes at most n steps to walk the part of the list before the cycle. Once both are inside, the gap is less than the length of the loop, which is at most n, and it shrinks by 1 per step. So that part also takes at most n steps. In total, at most about 2n steps, which is O(n).
Linked List Cycle II (LeetCode 142) asks for the node where the cycle begins. A small piece of arithmetic gives it.
Name three distances.
a: from the head to the start of the cycle.
b: from the start of the cycle to the node where slow and fast meet.
c: from the meeting node the rest of the way round, back to the start of the cycle. So the loop's length is b + c.
When they meet, slow has walked a + b. fast has walked twice as far, 2(a + b). But fast has also walked the same path as slow, plus some whole number of extra laps, call it k laps:
2(a + b) = a + b + k(b + c)
Take a + b away from both sides:
a + b = k(b + c)
Now take b away from both sides:
a = k(b + c) - b = (k - 1)(b + c) + c
Read that last line in words. The distance from the head to the cycle's start equals the distance from the meeting point to the cycle's start (c), plus some whole number of full laps. Full laps bring you back to where you began, so they do not change where you end up.
So: put one pointer back at the head, leave the other at the meeting point, and move both one step at a time. After a steps, the first one reaches the cycle's start. The second one has walked c plus some full laps, which also lands on the cycle's start. They meet there.
python
def detectCycle(self, head): slow = fast = head while fast and fast.next: slow, fast = slow.next, fast.next.next if slow is fast: # they met inside the cycle slow = head # restart one pointer at the head while slow is not fast: # both now move one step at a time slow, fast = slow.next, fast.next return slow # the start of the cycle return None
This technique is not really about linked lists. It works on any process where each state has exactly one next state, and it detects that the process eventually repeats.
Find the Duplicate Number. Treat each array value as a pointer to another position. The repeated value becomes the start of a cycle. That is the next page, 4.9.8, and it is the most surprising use of this idea.
Happy Number. Replace a number by the sum of the squares of its digits, again and again. Either you reach 1, or you go round a cycle. See 4.28.4.
The general lesson: when a process has exactly one next state, two pointers at different speeds detect repetition using no extra memory.
"Prove the pointers must meet." The gap shrinks by exactly one per step, so it cannot skip over zero.
"Why does fast move two and not three?" Gaining two per step can jump past zero without landing on it.
"Find where the cycle starts." Derive the algebra above. Deriving it, not reciting it, is what they are checking.
"What about the set version?"O(n) memory, simpler, and completely fine to give first.
One thing to volunteer: name the method, Floyd's cycle detection, and say it works on any process with one next state, not just lists. That leads straight into the next problem.