Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Constraints:
[0, 104].-105 <= Node.val <= 105pos is -1 or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
Problem Overview: You are given the head of a singly linked list and must determine whether the list contains a cycle. A cycle occurs when a node’s next pointer points to a previously visited node instead of null, creating an infinite loop during traversal.
Approach 1: HashSet Detection (O(n) time, O(n) space)
This approach tracks visited nodes using a hash-based data structure. Iterate through the linked list starting from the head and insert each node reference into a hash table (or HashSet). Before inserting, check whether the node already exists in the set. If it does, the traversal has reached the same node again, meaning a cycle exists. If you reach null, the list terminates normally and no cycle is present. The key insight is that a node inside a cycle must eventually repeat during traversal. This method is straightforward and easy to reason about, but it requires additional memory proportional to the number of visited nodes.
Approach 2: Floyd's Tortoise and Hare Algorithm (O(n) time, O(1) space)
This classic two pointers technique avoids extra memory. Maintain two pointers that traverse the list at different speeds: a slow pointer moving one step at a time and a fast pointer moving two steps at a time. If the list has no cycle, the fast pointer eventually reaches null. If a cycle exists, the fast pointer laps the slow pointer inside the loop, causing them to meet at the same node. The meeting point proves that the traversal is repeating. The insight is based on relative speed: inside a cycle, the faster pointer closes the distance between the two pointers until they collide. This approach is optimal because it scans the list once while using constant extra space.
Recommended for interviews: Floyd's Tortoise and Hare algorithm is the expected solution. Interviewers look for the ability to recognize the cycle-detection pattern and apply the two-pointer technique with O(n) time and O(1) space. Implementing the HashSet approach first still demonstrates clear understanding of the problem, but transitioning to the constant-space solution shows stronger algorithmic thinking.
The Floyd's Tortoise and Hare algorithm is a two-pointer technique that is used to detect cycles in a linked list. The approach involves using two pointers, one moving twice as fast as the other. If there's a cycle, the fast pointer will eventually meet the slow pointer. This method works in O(n) time with O(1) space.
In this solution, we create two pointers, slow and fast. The slow pointer moves one step at a time while the fast moves two steps. If the list contains a cycle, these pointers will eventually meet inside the cycle. If there's no cycle, fast or fast->next will become null.
Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1), constant space usage.
This approach uses a HashSet to track the nodes visited during the traversal. If a node is encountered twice, there is a cycle. This method requires O(n) space but is simpler to understand.
This C solution simulates a HashSet using an array to record visited nodes. By checking existing entries, it detects cycles but uses O(n) space.
Time Complexity: O(n^2) because of nested loops (non-optimal use of memory).
Space Complexity: O(n), where n is the number of nodes (uses additional storage).
We can traverse the linked list and use a hash table s to record each node. When a node appears for the second time, it indicates that there is a cycle, and we directly return true. Otherwise, when the linked list traversal ends, we return false.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the linked list.
Python
Java
C++
Go
TypeScript
We define two pointers, fast and slow, both initially pointing to head.
The fast pointer moves two steps at a time, and the slow pointer moves one step at a time, in a continuous loop. When the fast and slow pointers meet, it indicates that there is a cycle in the linked list. If the loop ends without the pointers meeting, it indicates that there is no cycle in the linked list.
The time complexity is O(n), and the space complexity is O(1), where n is the number of nodes in the linked list.
Python
Java
C++
Go
TypeScript
JavaScript
C#
| Approach | Complexity |
|---|---|
| Floyd's Tortoise and Hare Algorithm | Time Complexity: O(n), where n is the number of nodes in the list. |
| HashSet Approach | Time Complexity: O(n^2) because of nested loops (non-optimal use of memory). |
| Hash Table | — |
| Fast and Slow Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Detection | O(n) | O(n) | When simplicity and readability matter more than memory usage |
| Floyd's Tortoise and Hare | O(n) | O(1) | Optimal solution for interviews or memory-constrained environments |
Linked List Cycle - Floyd's Tortoise and Hare - Leetcode 141 - Python • NeetCode • 319,363 views views
Watch 9 more video solutions →Practice Linked List Cycle with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor