~20 minutes · Day 24 · fast/slow pointers · Python
Tonight you solve Linked List Cycle. Interviewers like it because the input looks tiny: just nodes and next pointers. The catch is that a bad loop can run forever. This lesson teaches the interview move that detects a loop without storing every node.
Move one pointer twice as fast; inside a cycle the gap shrinks by one each step, so they must eventually meet.
Picture two runners on a circular track. One runner moves one step at a time; the other moves two. Once both are on the track, the faster runner gains exactly one node per loop. If there is a cycle, the distance between them cannot avoid becoming zero forever.
Inside the loop, the faster pointer closes the circular gap by one node each iteration.
A linked list cycle means that following next can bring you back to the same node object again, not merely to another node with the same value (LeetCode statement). In Python, is checks whether two names refer to the same object (Python reference: identity comparisons). That is why the final check is slow is fast, not a value comparison.
The direct approach is to remember every node object you visit in a set. Sets are Python's built-in structure for distinct hashable objects (Python docs: set types).
def hasCycle(head):
seen = set() # nodes visited so far
cur = head
while cur:
if cur in seen: # same node reached twice
return True
seen.add(cur)
cur = cur.next
return False
This is O(n) time and O(n) space: fast enough, but the memory can grow with the list. The interview follow-up is the useful part: can you keep the time but remove the set?
Floyd's cycle-finding algorithm uses two moving references, often called the tortoise and hare (Wikipedia: cycle detection). If there is no cycle, the fast pointer falls off the end. If there is a cycle, fast eventually catches slow.
def hasCycle(head):
slow = fast = head # both start at the head
while fast and fast.next: # fast can safely move twice
slow = slow.next # slow moves one step
fast = fast.next.next # fast moves two steps
if slow is fast: # same node object
return True
return False # fast reached the end
The guard while fast and fast.next matters. Without it, fast.next.next can crash on a list with no cycle.
Middle of the Linked List: return the middle node of a linked list. Before reading on, predict the move: which pointer should move twice as fast, and where will the slow pointer be when fast reaches the end?
def middleNode(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # one step
fast = fast.next.next # two steps
return slow # halfway point
Same skeleton, different stopping rule. For cycle detection, meeting means “cycle.” For middle finding, fast reaching the end means slow is halfway through.
The middle problem uses the same two speeds, but the signal is the end of the list instead of a meeting point.
| Approach | Time | Space |
|---|---|---|
| Memory set (remember every node) | O(n) | O(n) |
| Floyd fast/slow pointers | O(n) | O(1) |
The time stays linear. The win is that the pointer version uses only two references no matter how long the list is.
1. What does fast do each loop?
fast moves two nodes while slow moves one. That speed difference is what makes the gap close inside a cycle.2. Spot the bug in this loop:
while fast:
slow = slow.next
fast = fast.next.nextfast. If fast.next is None, then fast.next.next crashes. Use while fast and fast.next.3. Which problem is this pattern?
4. Inside a cycle, what changes each step?
Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:
Watch NeetCode — Linked List Cycle after your attempt, as the compare step. Find the exact moment where his pointer reasoning matches or corrects yours.