Linked List Cycle
A linked list is stored in the array next: node i links to node next[i], and -1 means the list ends there. The head is node 0. Follow the links from the head and return true if you ever come back to a node you have already visited, or false if you reach the end. Nodes the walk never reaches do not count, even if they link to each other in a loop.
Function
- nextinteger-array
- the link of every node: next[i] is the node after node i, or -1
- Returnsboolean
- true if the walk from node 0 revisits a node, false if it reaches -1
Constraints
1 ≤ next.length ≤ 104-1 ≤ next[i] ≤ next.length-1- Several nodes may link to the same node, and some nodes may be unreachable from the head.
Examples
- Input
- next = [1, 2, 3, 1]
- Output
- true
- Explanation
- The walk goes 0, 1, 2, 3 and then back to 1. Node 1 is visited twice, so the list has a cycle through nodes 1, 2 and 3.
- Input
- next = [2, -1, 1]
- Output
- false
- Explanation
- The walk goes 0, 2, 1 and then reaches
-1: three different nodes and then the end, so there is no cycle.
- Input
- next = [-1, 2, 1]
- Output
- false
- Explanation
- Node 0 links to
-1, so the list is one node long. Nodes 1 and 2 link to each other in a loop, but the walk from the head never reaches them.
Follow-up
Can you also find the node where the cycle begins, still with O(1) extra memory?
Hints
Open them one at a time. Each one gives away a little more.
Walk from node 0 by following
next. A list without a cycle stops at-1, but a list with one never stops. What would you need to remember to notice that you are going around in circles?Marking visited nodes works but needs memory for every node. Instead, send two pointers down the list at different speeds. What happens to the distance between them if the list loops?
Move
slowone link andfasttwo links per round. Iffastornext[fast]is-1, there is no cycle. If the two pointers ever land on the same node, there is one.
Solution
A list with a cycle never reaches -1, so you cannot wait for the end. Remembering every visited node detects the loop with O(n) memory. Floyd's fast and slow pointers detect it with two integers, because a pointer moving twice as fast must catch the slow one inside a loop.
Mark the nodes you visit
Intuition
Walk from node 0 and mark each node as you leave it. Arriving at a marked node means the walk has come back, and from there it repeats forever. In example 1 you mark 0, 1, 2 and 3, and node 3 links to node 1, which is marked.
Nodes are numbered 0 to n-1, so a boolean array of length n serves as the visited set. The walk stops within n steps: O(n) time and O(n) memory for the marks.
Algorithm
- Create a boolean array
visitedof lengthn, all false. - Set
node = 0. - While
nodeis not-1, returntrueifvisited[node]is already true. - Otherwise set
visited[node]and move tonext[node]. - When the walk reaches
-1, returnfalse.
def hasCycle(next):
visited = [False] * len(next)
node = 0
while node != -1:
if visited[node]:
return True # back at a node already on the path
visited[node] = True
node = next[node]
return FalseFast and slow pointers (Floyd's cycle detection)
Intuition
slow follows one link per round and fast follows two. If the list ends, fast reaches -1 first. If there is a cycle, fast enters it and keeps circling until slow arrives.
Once both are in the cycle, fast gains exactly one node on slow each round. The gap drops by one per round, so it reaches zero and the pointers land on the same node; it cannot skip past zero.
In example 1, after one round slow is on node 1 and fast on node 2. After two, slow is on 2 and fast on 1. After three, both are on node 3.
slow enters the cycle within n rounds, and they meet before it finishes one lap: O(n) time, two integers of memory.
Algorithm
- Set
slow = 0andfast = 0. - While
fastis not-1andnext[fast]is not-1, moveslowone link andfasttwo links. - After each move, return
trueif they are on the same node. - When the loop stops,
fastfound the end: returnfalse.
def hasCycle(next):
slow = 0
fast = 0
# fast needs two links to move; if either is missing, the list ends.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
if slow == fast:
return True
return False
Pitfalls and edge cases
- Moving
fasttwo links without checking both.fastandnext[fast]must be real nodes before you readnext[next[fast]]; otherwise you readnext[-1], which crashes, or in Python silently reads the last element. - Comparing the pointers before moving them. Both start at node 0, so a check at the top of the loop reports a cycle in every list.
- Looking at the whole array instead of the walk. In
[-1, 2, 1]nodes 1 and 2 loop out of reach of the head, so the answer isfalse. Nor is a repeated value a cycle: in[4, 4, 4, 4, -1]four nodes link to node 4. - Assuming a cycle must lead back to the head. In
[1, 2, 3, 4, 4]the last node links to itself.
Frequently asked questions4
How does Floyd's cycle detection work?
Two pointers start at the head: one moves one link per step, the other two. Without a cycle the fast one reaches the end. With a cycle both end up inside it, the fast one closes the gap by one node per step, and they meet on the same node.
What is the time and space complexity of Linked List Cycle?
Both approaches take O(n) time. Marking visited nodes needs O(n) extra memory. Floyd's fast and slow pointers need O(1): two node numbers.
Can you detect a cycle with a hash set?
Yes. In a list built from objects, put each node reference in a hash set and report a cycle when one is already there. It runs in O(n) time but uses O(n) memory, which is why interviewers ask for Floyd's method next.
Can you detect the cycle by counting steps?
In this array form, yes: a list without a cycle reaches -1 within n links, so walking n links without reaching the end proves a cycle. A list made of pointers does not give you n, and counting the nodes first never finishes when there is a cycle.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def hasCycle(next):
# Write code hereTest #1
Test #2
Test #3
Argument
next = [1, 2, 3, 1]
Expected Output
true