Linked List Cycle
Problem Statement
Given the head of a linked list, determine whether the list contains a cycle. A cycle exists when some node can be reached again by continuously following next pointers.
The input may describe pos, the index where the tail connects back, but pos is not passed to the function. Your method receives only head and must detect the structure from pointers.
Input
The head pointer of a singly linked list. The test harness may connect the tail back to an earlier node.
Output
A boolean: true if the linked list contains a cycle, otherwise false.
Constraints
- •
The number of nodes is in the range 0 to 10^4 - •
-10^5 <= Node.val <= 10^5 - •
pos is -1 or a valid node index in the list
Examples
Example 1
head = [3,2,0,-4], pos = 1
trueExample 2
head = [1,2], pos = 0
trueExample 3
head = [1], pos = -1
falseLearning Objectives
- Recognise the fast and slow pointer signal for cycle detection.
- Explain why a fast pointer must eventually catch a slow pointer inside a cycle.
- Contrast Floyd's O(1)-space approach with the O(n)-space visited-set approach.
- Guard pointer movement so **fast.next.next** is never evaluated after null.
Intuition
Pattern Recognition
A cycle question asks whether following next pointers can continue forever. That is the fast and slow pointer signal: use two walkers on the same path, one moving one step and the other moving two steps.
If the list has no cycle, fast reaches null first because it consumes the list faster. If the list has a cycle, both pointers eventually enter the loop. Once inside, fast gains one node on slow every move, so the distance between them around the cycle closes until they meet.
A visited set is also valid: record every node reference and return true when a node appears again. It is easier to reason about, but it spends O(n) extra space. Floyd's method keeps the same detection power with O(1) space.
Common mistakes
- ×Checking node values instead of node references; duplicate values do not imply a cycle.
- ×Moving **fast.next.next** without first verifying both **fast** and **fast.next** are not null.
- ×Starting two pointers but moving both one step, which preserves their distance forever.
- ×Using a set as the only solution without mentioning the O(1)-space Floyd tradeoff.
Algorithm Explanation
Key idea
Run slow one step at a time and fast two steps at a time. Null means the list ends, so there is no cycle. Pointer equality means both references point to the same node, so a cycle exists.
Pointer walkthrough
For 3 -> 2 -> 0 -> -4 -> 2 ..., start both pointers at 3. After one move, slow is at 2 and fast is at 0. After two moves, slow is at 0 and fast has wrapped to 2. After three moves, slow reaches -4 and fast also reaches -4. The catch proves the loop.
Without the cycle, the same two-step movement would eventually push fast to null, which proves the list is finite.
Algorithm
- Set slow = head and fast = head.
- While fast and fast.next are both not null, move slow one step and fast two steps.
- If the two pointers ever reference the same node, return true.
- If the loop ends because fast reached the tail, return false.
Solutions
Solution 1: Floyd tortoise and hare
Use this in interviews as the expected optimal solution when the list must be inspected in O(1) extra space.
The fast pointer moves twice as quickly as the slow pointer. In an acyclic list, fast reaches null. In a cyclic list, fast eventually laps slow inside the cycle, so pointer equality detects the loop.
Step-by-step
- Initialise slow and fast at head.
- Continue only while fast and fast.next are safe to advance.
- Move slow by one node and fast by two nodes.
- Return true as soon as the two references match.
- Return false if fast reaches the end of the list.
O(n)
O(1)
Each pointer makes at most a linear number of moves before null or a meeting occurs.
Java implementation
Solution 2: Visited node set
Use this when you want the simplest correctness story and O(n) extra space is acceptable.
Store every node reference as it is visited. If traversal reaches a node already in the set, the list has looped back. If traversal reaches null, the list is acyclic.
Step-by-step
- Create an empty set of visited node references.
- Walk through the list with current.
- If current is already in the set, return true.
- Otherwise add current and advance to current.next.
- Return false if traversal reaches null.
O(n)
O(n)
Each reachable node is visited once, and up to n node references are stored.
Java implementation
Dry Run
Sample input
head = 3 -> 2 -> 0 -> -4, with the tail pointing back to the node 2.
| move | slow | fast | result |
|---|---|---|---|
| start | 3 | 3 | no decision yet |
| 1 | 2 | 0 | different nodes |
| 2 | 0 | 2 | different nodes after fast wraps |
| 3 | -4 | -4 | same node, cycle found |
The fast pointer catches the slow pointer at -4, so the method returns true before any pointer reaches null.
Interview Tips
Lead with the invariant: if there is a cycle, relative speed inside the loop is one node per move, so a catch is inevitable. Say explicitly that equality compares node references, not values. Then mention the hash-set alternative as a clear O(n)-space tradeoff, not as a brute-force method.
Likely follow-ups
- How would you return the node where the cycle begins?
- How would you compute the length of the cycle after detecting it?
- What changes if the list is circular by design and every node is expected to have a next pointer?
- How would you detect a cycle in an implicit state machine instead of a materialized list?
Similar Problems
Key Takeaways
- Fast and slow pointers detect whether a linked structure loops forever.
- In a cycle, the fast pointer gains one node per move and must eventually meet slow.
- A hash set gives a simpler O(n)-space alternative, while Floyd uses O(1) space.
- Always guard **fast** and **fast.next** before moving two steps.