Watch 10 video solutions for Linked List Cycle, a easy level problem involving Hash Table, Linked List, Two Pointers. This walkthrough by NeetCode has 319,363 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |