Where it runs
1. The problem
You walk along a chain of { val, next } nodes and need to answer one of two questions. The first: does the chain loop back on itself, so you could follow next forever? The second you already solved in the previous lesson: if there is no loop, which node stands in the middle when the length is not known in advance?
Loops in chains happen in practice. A task scheduler links jobs with "run after" links. One mistake in the settings, and job A waits for B while B waits for A. Follow such a chain and you never stop. The scheduler hangs.
The first idea that comes to mind: write every node you pass into a set (a Set) and stop at the first node you meet a second time. That works, but on a huge chain the set grows to the size of the whole list. There is a way to answer both questions with two variables.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedhasCycle(1 → 2 → 3 → 4 → 5 → 6 → back to 3)Does the list loop? The last node, 6, points back to 3. Both pointers start at the head.
Recognise it
Say these words and it is this pattern
- detect a cycle in a linked list
- find where a cycle begins
- find the middle node of a list
- determine if a list is a palindrome
- no extra memory / O(1) space, only pointers
Looks similar, isn't
- Two pointers (same direction)
There one pointer reads and the other writes. Here both read, at different speeds.
- Hash set / map
A set of visited nodes also catches a cycle. It costs O(n) memory instead of O(1).
- Linked list reversal
Reversal rewires the links themselves. This pattern never changes a pointer in the list.
- Graph BFS / DFS
A traversal finds cycles in any graph, with a visited set. This works because each node has one exit.
n up to 1e6 gives O(n) time and O(1) space. The slow pointer never walks more than n steps.
On LeetCode
Problems that ask whether following next pointers ever loops and where the loop starts, including loops hidden in numbers or array values. Two walkers at different speeds answer with O(1) memory.
This is hasCycle from the lesson.
This is cycleEntry, with the second walk starting from the head after the meeting.
The digit-square step works as a next pointer, so fast and slow show whether you reach 1 or loop.
Read each value as a next pointer, and the loop entry is the repeated number.