Linked List Cycle Detection
Problem
Given the head of a linked list, determine if the linked list contains a cycle. Return true if there is a cycle in the linked list, otherwise return false.
- The number of nodes in the list is in the range [0, 10⁴]
- −10⁵ ≤ Node.val ≤ 10⁵
- pos is −1 or a valid index in the linked list
Example
head = [3,2,0,-4], pos = 1trueThe linked list contains a cycle because the tail connects to the node at position 1 (0-indexed). The algorithm uses two pointers starting at the head: 'slow' moves one step at a time, 'fast' moves two steps. Initially, both point to the node with value 3. After the first iteration, slow points to 2, fast points to 0. After the second iteration, slow points to 0, fast points to 2. Eventually, slow and fast meet at the node with value 2, confirming a cycle.
Approach
Straightforward Solution
A brute-force approach uses a hash set to record visited nodes and checks for repeats. This requires O(n) space and is less efficient.
Core Observation
If a linked list contains a cycle, two pointers moving at different speeds will eventually meet inside the cycle. If no cycle exists, the fast pointer will reach the end of the list (null) without meeting the slow pointer.
Path to Optimal
The key recognition signals are 'detect cycle' and 'linked list traversal'. These indicate the Fast & Slow Pointers pattern because it uses two pointers moving at different speeds to detect cycles in O(1) space. The fast pointer moves twice as fast as the slow pointer, so if a cycle exists, the fast pointer laps the slow pointer inside the cycle.
Optimal Approach
Initialize two pointers at the head. Move slow by one node and fast by two nodes in each iteration. If at any point slow equals fast, return true indicating a cycle. If fast or fast.next becomes null, return false indicating no cycle.
Time
O(n)
Each pointer traverses the list at most once. The fast pointer moves through nodes twice as fast, so the meeting occurs in linear time relative to the list length.
Space
O(1)
Only two pointers are used regardless of input size, so the auxiliary space is constant.
Pattern Spotlight
Fast & Slow Pointers (Cycle Detection in Linked List)
When detecting cycles in linked structures, use two pointers moving at different speeds; if a cycle exists, the faster pointer will eventually catch up to the slower one inside the cycle.
Solution
| 1 | class Solution:
|
| 2 | def hasCycle(self, head: ListNode) -> bool:
|
| 3 | slow, fast = head, head
|
| 4 |
|
| 5 | while fast and fast.next:
|
| 6 | slow = slow.next
|
| 7 | fast = fast.next.next
|
| 8 | if slow == fast:
|
| 9 | return True
|
| 10 |
|
| 11 | return False |
| 1 | class Solution { |
| 2 | public boolean hasCycle(ListNode head) { |
| 3 | ListNode slow = head; |
| 4 | ListNode fast = head; |
| 5 | |
| 6 | while (fast != null && fast.next != null) { |
| 7 | slow = slow.next; |
| 8 | fast = fast.next.next; |
| 9 | if (slow == fast) { |
| 10 | return true; |
| 11 | } |
| 12 | } |
| 13 | |
| 14 | return false; |
| 15 | } |
| 16 | } |
| 1 | #include <cstddef> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | bool hasCycle(ListNode *head) { |
| 8 | ListNode *slow = head; |
| 9 | ListNode *fast = head; |
| 10 | |
| 11 | while (fast != nullptr && fast->next != nullptr) { |
| 12 | slow = slow->next; |
| 13 | fast = fast->next->next; |
| 14 | if (slow == fast) { |
| 15 | return true; |
| 16 | } |
| 17 | } |
| 18 | |
| 19 | return false; |
| 20 | } |
| 21 | }; |
| 1 | var hasCycle = function(head) { |
| 2 | let slow = head; |
| 3 | let fast = head; |
| 4 | |
| 5 | while (fast !== null && fast.next !== null) { |
| 6 | slow = slow.next; |
| 7 | fast = fast.next.next; |
| 8 | if (slow === fast) { |
| 9 | return true; |
| 10 | } |
| 11 | } |
| 12 | |
| 13 | return false; |
| 14 | }; |
Step-by-Step Solution
Initialize Slow and Fast Pointers at Head
| 3 | slow, fast = head, head
|
Objective
To set up two pointers starting at the head of the linked list for cycle detection.
Key Insight
Starting both pointers at the head ensures they traverse the same path initially. The difference in their speeds will reveal the presence of a cycle without extra space. This initialization is the foundation for the fast and slow pointer technique.
Interview Quick-Check
Core Logic
Both pointers start at the head to synchronize traversal and enable cycle detection through relative movement.
Common Pitfalls & Bugs
Failing to initialize both pointers at the head can cause incorrect detection or missed cycles.
Advance Pointers and Detect Cycle by Meeting
| 5 | while fast and fast.next:
|
| 6 | slow = slow.next
|
| 7 | fast = fast.next.next
|
| 8 | if slow == fast:
|
| 9 | return True
|
Objective
To move slow by one step and fast by two steps, checking for pointer equality to detect a cycle.
Key Insight
The slow pointer moves one node at a time, while the fast pointer moves two nodes. If a cycle exists, the fast pointer will eventually lap the slow pointer inside the cycle, causing them to meet. If no cycle exists, the fast pointer will reach the end (null) first, confirming no cycle.
Interview Quick-Check
Core Logic
Moving pointers at different speeds exploits the cycle's structure to guarantee a meeting point if a cycle exists.
State & Boundaries
The loop continues only while fast and fast.next are not null, ensuring safe pointer advancement.
Common Pitfalls & Bugs
Not checking fast and fast.next before advancing fast pointer can cause null pointer exceptions.
Complexity
This approach achieves O(n) time and O(1) space, optimal for cycle detection.
Return False if No Cycle Detected
| 11 | return False |
Objective
To return false when the fast pointer reaches the end of the list, indicating no cycle.
Key Insight
If the fast pointer or its next node is null, the list terminates without cycles. Returning false here correctly signals the absence of a cycle after exhaustive traversal.
Interview Quick-Check
Core Logic
Returning false after the loop confirms that no cycle was found during traversal.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
fast = fast.next.nextMove fast pointer two steps forward.
This line is the critical step that creates the speed difference between pointers, enabling the fast pointer to catch up to the slow pointer inside a cycle, which is the fundamental mechanism for cycle detection.
if slow == fast:Check if slow and fast pointers have met.
This equality check is the definitive condition for cycle detection; if slow equals fast, the linked list contains a cycle, and the algorithm can terminate early.
slow, fast = head, headInitialize slow and fast pointers to the head of the linked list.
Starting both pointers at the head synchronizes their traversal paths, enabling the fast pointer to eventually catch up to the slow pointer if a cycle exists.
return TrueReturn true indicating a cycle is detected.
Returning true immediately upon pointer meeting efficiently terminates the search, confirming the cycle's existence.
return FalseReturn false indicating no cycle was found.
If the fast pointer reaches the end of the list, no cycle exists, so returning false correctly signals this outcome.
while fast and fast.next:Continue looping while fast and fast.next are not null.
This condition ensures safe advancement of the fast pointer by two steps without causing null pointer exceptions, maintaining loop correctness.
slow = slow.nextMove slow pointer one step forward.
Advancing slow by one node maintains the relative speed difference essential for detecting cycles via pointer meeting.
Test Your Understanding
Why does the fast pointer eventually meet the slow pointer if a cycle exists?
Because the fast pointer moves two steps at a time and the slow pointer moves one step, the fast pointer gains one node per iteration on the slow pointer inside the cycle, guaranteeing they meet eventually.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Linked List Cycle Detection from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Linked List Cycle Detection drill