Watch 10 video solutions for Linked List Cycle, a easy level problem involving Hash Table, Linked List, Two Pointers. This walkthrough by NeetCode has 256,974 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: Given the head of a singly linked list, determine whether the list contains a cycle. A cycle occurs when a node’s next pointer points back to a previously visited node instead of null.
Approach 1: HashSet (O(n) time, O(n) space)
Traverse the list while storing every visited node reference in a hash set. On each step, check whether the current node already exists in the set using a constant-time hash lookup. If the node appears again, the traversal has looped back to an earlier node, which confirms a cycle. If the traversal reaches null, the list ends normally and no cycle exists.
This approach is straightforward because it directly tracks visited nodes. The key operation is inserting node references into a hash table and checking membership on every iteration. The tradeoff is extra memory proportional to the number of nodes visited. Hash-based detection is often used when clarity matters more than strict space optimization. This technique relies on a hash table and basic traversal of a linked list.
Approach 2: Floyd's Tortoise and Hare Algorithm (O(n) time, O(1) space)
This method uses two pointers moving at different speeds through the list. The slow pointer advances one node at a time, while the fast pointer advances two nodes at a time. If a cycle exists, the faster pointer eventually laps the slower one and both pointers reference the same node. If the fast pointer reaches null or fast.next becomes null, the list terminates and no cycle exists.
The key insight is that in a cyclic structure, two pointers moving at different speeds must eventually meet. Once both pointers enter the cycle, the fast pointer closes the distance by one node each iteration. This guarantees an intersection within at most one full cycle traversal. The algorithm uses only pointer movement and comparisons, so memory usage remains constant. This technique is a classic two pointers pattern adapted for linked lists.
Floyd’s algorithm is preferred in production code because it avoids auxiliary data structures and still guarantees linear traversal. The logic is slightly less intuitive than the hash set approach, but it scales better for large lists where memory overhead matters.
Recommended for interviews: Floyd's Tortoise and Hare algorithm. Interviewers expect candidates to recognize the cycle detection pattern using two pointers with O(n) time and O(1) space. Mentioning the HashSet approach first demonstrates understanding of the problem, but implementing the two-pointer technique shows stronger algorithmic reasoning and familiarity with common linked list patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet (Visited Nodes) | O(n) | O(n) | When clarity is preferred and extra memory is acceptable |
| Floyd's Tortoise and Hare | O(n) | O(1) | Optimal interview solution and memory-constrained environments |