Where a linked list loops back on itself
Medium · Target 15 minutes · Two pointers· Type asked at
LinkedIn
Bank of America
Two Sigma
A singly linked list is stored as an array next, where next[i] is the index of
the node after node i, or −1 if node i is the last one. The list starts at node 0. If
following it from node 0 goes round a cycle, return the index of the first node of that cycle (the first node you
reach twice). If the list ends, return −1. You should only use O(1) extra space.
Examples
| Input | Output | Why |
|---|---|---|
next = [1, 2, 3, 1] | 1 | The list goes 0 → 1 → 2 → 3 and then back to 1, so it's at 1 that the cycle starts. |
next = [1, -1] | -1 | 0 → 1 and then the list ends, so there's no cycle. |
next = [0] | 0 | Node 0 points to itself, which is a cycle of length one. |
Constraints
- 1 ≤ n ≤ 10⁴
- −1 ≤ next[i] < n
Hints
Hint 1
A set of the nodes you've visited would do it in O(n) space. How would you even tell whether there's a cycle without remembering anything?
Hint 2
Run a slow pointer one step at a time and a fast one two steps. If fast falls off the end there's no cycle. If there's a cycle they'll meet in it.
Hint 3
Once they've met, put one pointer back at node 0 and move both one step at a time. The node where they meet now is where the cycle starts.
Where people lose marks
- Moving fast two steps without checking the first one. If next[fast] is −1 you can't go on to look up next[−1], so you've got to check before each of the two steps.
- Returning the node where they first met, which is on the cycle all right but it's only the first node of it if the path in happens to be the right length.
- Starting slow and fast on the same node with the check at the top of the loop, so that they're equal straight away and you'd report a cycle that isn't there.
Dry run on [2,3,4,1,5,3]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 10next20slow/fast3142135435slow0fast0
I'd write out the start of the list first, which goes 0 → 2 → 4 → 5 and on from there, and both pointers start out on node 0.
-
Step 2 / 10next203142slow1354fast35slow2fast4
slow steps to node 2 and fast jumps two to node 4.
-
Step 3 / 10next20314213fast54slow35slow4fast3
Now slow is on 4 and fast has got to 3.
-
Step 4 / 10next20314213fast5435slowslow5fast3
slow steps to node 5 and fast jumps two to node 3.
-
Step 5 / 10next20314213slow/fast5435slow3fast3
They meet at node 3, which is somewhere on the cycle.
-
Step 6 / 10next20a314213slow5435a0slow3
Now one of them goes back to node 0 while the other one stays where they met, and from here on both of them move a single step at a time.
-
Step 7 / 10next2031slow42a135435a2slow1
a moves to 2 and slow moves to 1.
-
Step 8 / 10next20314213slow54a35a4slow3
a moves to 4 and slow moves to 3.
-
Step 9 / 10next2031slow42135435aa5slow1
a moves to 5 and slow moves to 1.
-
Step 10 / 10next20314213a/slow5435a3slow3
They meet at node 3, and that's where the cycle starts.
How to think about it
This is Floyd's method on a list that might just end, and I think it's the version you're most likely to
be asked in an interview. In the first phase the slow pointer follows next once on each step and the
fast one follows it twice. If the fast one gets to −1 (or is about to step off a node whose next is −1) then the
list ends and you'd return −1. If it doesn't they're both going round a cycle with the fast one catching up a step
at a time, so sooner or later they'll meet.
For the second phase I'd put one pointer back at node 0 and leave the other one where they met, and then move both of them one step at a time. If the path into the cycle is a nodes long and they met b steps past its start then a + b is a whole number of laps, so a steps on from where they met takes you to the start of the cycle. The pointer that set off from node 0 gets there after a steps as well, which is why they meet exactly on it.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def detect_cycle(next):
slow = fast = 0
while True: # phase 1: meet on the cycle, or fall off the end
if fast == -1 or next[fast] == -1:
return -1
slow = next[slow]
fast = next[next[fast]]
if slow == fast:
break
a = 0
while a != slow: # phase 2: walk in to the start of the cycle
a = next[a]
slow = next[slow]
return a#include <vector>
int solve(const std::vector<int>& next) {
int slow = 0, fast = 0;
for (;;) { // phase 1: meet on the cycle, or fall off the end
if (fast == -1 || next[fast] == -1) return -1;
slow = next[slow]; fast = next[next[fast]];
if (slow == fast) break;
}
int a = 0;
while (a != slow) { a = next[a]; slow = next[slow]; } // phase 2: walk in to the start
return a;
}class Solution {
public int detectCycle(int[] next) {
int slow = 0, fast = 0;
while (true) { // phase 1: meet on the cycle, or fall off the end
if (fast == -1 || next[fast] == -1) return -1;
slow = next[slow]; fast = next[next[fast]];
if (slow == fast) break;
}
int a = 0;
while (a != slow) { a = next[a]; slow = next[slow]; } // phase 2: walk in to the start
return a;
}
}function detectCycle(next) {
let slow = 0, fast = 0;
for (;;) { // phase 1: meet on the cycle, or fall off the end
if (fast === -1 || next[fast] === -1) return -1;
slow = next[slow]; fast = next[next[fast]];
if (slow === fast) break;
}
let a = 0;
while (a !== slow) { a = next[a]; slow = next[slow]; } // phase 2: walk in to the start
return a;
}fn solve(next: &[i64]) -> i64 {
let at = |i: i64| next[i as usize];
let (mut slow, mut fast) = (0i64, 0i64);
loop { // phase 1: meet on the cycle, or fall off the end
if fast == -1 || at(fast) == -1 { return -1; }
slow = at(slow); fast = at(at(fast));
if slow == fast { break; }
}
let mut a = 0;
while a != slow { a = at(a); slow = at(slow); } // phase 2: walk in to the start
a
}import Data.Array
solve :: [Int] -> Int
solve xs = phase1 0 0
where
arr = listArray (0, length xs - 1) xs
nx i = arr ! i
-- phase 1: meet on the cycle, or fall off the end
phase1 s f
| f == -1 || nx f == -1 = -1
| s' == f' = phase2 0 s'
| otherwise = phase1 s' f'
where s' = nx s
f' = nx (nx f)
-- phase 2: walk in to the start of the cycle
phase2 a s | a == s = a
| otherwise = phase2 (nx a) (nx s)Variants to try
- If you're asked for the length of the cycle, keep one pointer where they met and walk the other round until it comes back, counting steps.
- If two lists can merge into one, you can find where by joining the tail of one to the head of the other and running this, then undoing the join.
Next problems
The repeated number, without changing the array
Read the array as a list where index i points to nums[i]. The repeated value is where two arrows meet, which is the start of a cycle, and Floyd finds it in O(1) space.
Open the problem → Easy10 minDoes the digit-square sequence reach 1
Replace n by the sum of the squares of its digits, again and again. Either you hit 1 or you go round a loop, and a fast and a slow pointer tell you which without storing anything.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem →Write a solution and run it against the real test table.
Keep going
The repeated number, without changing the array
Read the array as a list where index i points to nums[i]. The repeated value is where two arrows meet, which is the start of a cycle, and Floyd finds it in O(1) space.
Open the problem → Easy10 minDoes the digit-square sequence reach 1
Replace n by the sum of the squares of its digits, again and again. Either you hit 1 or you go round a loop, and a fast and a slow pointer tell you which without storing anything.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.