A singly linked list either ends in None or, because some node’s next points back to an earlier node, loops forever. Asking “does this list have a cycle?” is easy with extra memory and surprisingly elegant without it. The constant-memory version, usually credited to Robert Floyd and nicknamed the tortoise and the hare, is one of those algorithms interviewers like because it rewards understanding over memorisation: the code is six lines, but the follow-up questions test whether you know why it works.
The version with a hash set
Start with the straightforward answer, because it’s correct and you should say it first. Walk the list, remember every node you’ve visited, and if you ever reach one you’ve seen, there’s a cycle:
def has_cycle_set(head):
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return FalseThis is O(n) time and O(n) space. Note that it stores nodes, not values. Two different nodes can hold the same value (1 → 1 → 1) without any cycle, so if head.val in seen would be wrong. Python’s default object hashing uses identity, which is what you want here.
The follow-up is always the same: can you do it in O(1) extra space?
Two pointers at different speeds
Start two pointers at the head. slow moves one node per step; fast moves two. If the list ends, fast reaches None first and there’s no cycle. If there’s a cycle, both pointers eventually enter it and go round forever, and the claim is that they must land on the same node.
The reason is simple once you see it. Once both are inside the cycle, look at how far fast is behind slow, measured forward around the loop. Every step, slow moves one forward and fast moves two, so that gap shrinks by exactly one. A gap that shrinks by one each step can’t jump from 1 to -1; it has to hit 0. So fast can’t leap over slow, and they meet within one lap of slow entering the cycle.
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def has_cycle(head):
slow = fast = head
while fast and fast.next: # both checks, in this order
slow = slow.next
fast = fast.next.next
if slow is fast: # identity, not equal values
return True
return FalseA small helper builds a list from values and, if pos >= 0, links the tail back to the node at that index. Testing the edge cases interviewers care about:
[3, 2, 0, -4] pos=1: True
[1, 2] pos=0: True
[1] pos=0: True
[1] pos=-1: False
[] pos=-1: False
[1, 2, 3, 4, 5] pos=-1: FalseA single node pointing to itself is a cycle and is detected. An empty list never enters the loop. Total work is O(n): slow takes at most n steps before the meeting, and fast does twice that. Extra space is two pointers.
The null check that crashes even-length lists
The loop condition fast and fast.next is where hand-written versions break. fast moves two steps, so before advancing you need both fast and fast.next to exist. A common slip checks only fast.next:
while fast.next: # forgot to check fast itself
slow = slow.next
fast = fast.next.nextOn [1, 2, 3, 4] with no cycle, fast goes 1 → 3 → None. On the next check, fast is None, and Python reports:
AttributeError: 'NoneType' object has no attribute 'next'Odd-length lists happen to survive because fast stops on the last node rather than past it, which is why this bug can slip through a quick test with [1, 2, 3]. The order of the two conditions matters as well: fast and fast.next short-circuits, so fast.next is never evaluated when fast is None. In JavaScript the same guard reads while (fast !== null && fast.next !== null), and the error you’d see without it is TypeError: Cannot read properties of null (reading 'next').
Finding where the cycle starts
Detection is half the story. The classic follow-up asks for the node where the cycle begins, still in O(1) space. After the pointers meet, move one of them back to the head and advance both one step at a time. The node where they meet again is the entry.
def cycle_entry(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
break
else:
return None # fast fell off the end: no cycle
slow = head # phase 2: one pointer back to the head
while slow is not fast:
slow, fast = slow.next, fast.next # both move one step now
return slowWith a print added at the meeting point, two lists show it working. The first is 3 → 2 → 0 → -4 with -4 linking back to 2. The second is the values 0 to 9 with the tail linking back to 6:
met at node -4 after 3 steps
cycle starts at node 2
met at node 8 after 8 steps
cycle starts at node 6Here’s why the reset works. Let a be the number of steps from the head to the cycle entry, b the steps from the entry to the meeting point, and c the cycle length. When they meet, slow has walked a + b, and fast has walked twice that. fast also walked a + b plus some whole number of laps, k · c. So 2(a + b) = a + b + k · c, which simplifies to a = k · c - b. In words: walking a steps from the meeting point is the same as walking back b steps (to the entry) and then going round k - 1 full laps, which lands you on the entry again. A pointer starting at the head reaches the entry after exactly a steps too, so they arrive together.
Check it against the second list: a = 6 (head to node 6), c = 4 (nodes 6, 7, 8, 9), and they met at node 8, so b = 2. Then k · c - b = 2 · 4 - 2 = 6, which equals a.
If you also need the cycle’s length, keep one pointer at the meeting point and walk the other around until it returns, counting steps.
The same trick on lists you can’t see
Fast and slow pointers show up beyond cycle detection. Running the same loop on a list without a cycle, slow ends at the middle when fast runs out. For [1, 2, 3, 4, 5] it stops on 3, and for [1, 2, 3, 4, 5, 6] it stops on 4, the second of the two middles. That’s the first step of Reorder List, which splits a list in half, reverses the second half and interleaves the two. If you need the first middle on even lengths, start fast at head.next instead.
A related idea, two pointers a fixed distance apart, solves Remove Nth Node From End of List in one pass.
Interview practice: find the duplicate number
You’re given an array of n + 1 integers where every value is between 1 and n, so at least one value repeats. Exactly one value is repeated, possibly more than once. Find it without modifying the array and using only O(1) extra space. For [1, 3, 4, 2, 2] the answer is 2.
Answer
Sorting modifies the array, and a set uses O(n) space, so neither is allowed. The insight is to read the array as a linked list: index i is a node whose next pointer is nums[i]. Every value is a valid index (between 1 and n), so following pointers never falls off the array, and since there are n + 1 nodes but only n possible targets, the walk from index 0 must eventually loop. Index 0 is never a target (no value is 0), so it’s outside the loop, like the head of a list.
The duplicated value is a node with two incoming pointers: two different indexes both point to it. That’s exactly what a cycle entry is (one pointer from the path leading in, one from the end of the loop). So run Floyd’s algorithm on the implicit list and return the entry:
def find_duplicate(nums):
# Treat index i as a node whose next pointer is nums[i].
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
print(find_duplicate([1, 3, 4, 2, 2]), find_duplicate([3, 1, 3, 4, 2]),
find_duplicate([2, 2, 2, 2, 2]), find_duplicate([1, 1]))2 3 2 1
2,000 random arrays: matches a counting checkThe second line comes from a randomised test that built shuffled arrays with one repeated value and compared the result with a simple count. Time is O(n), space O(1), and the array is only read. Unlike the linked-list version, there’s no None check: the loop is guaranteed to exist by the pigeonhole argument above. Being able to explain why the array forms a cycle, and why the entry is the duplicate, is what the interviewer is looking for; the code is just the algorithm you already know.