Watch 10 video solutions for Linked List Cycle II, a medium 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 the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1 Output: no cycle 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 linked list, detect whether a cycle exists and return the node where the cycle begins. If the list has no cycle, return null. The challenge is identifying the exact entry point of the loop rather than just detecting the loop.
Approach 1: Hash Table (O(n) time, O(n) space)
This approach walks through the list while storing each visited node in a hash set. For every node, check if it already exists in the set. The first node that appears twice is the start of the cycle because traversal re-enters the loop at that point. Each step performs a constant-time hash lookup and insertion, resulting in O(n) time complexity and O(n) extra space. The implementation is straightforward and useful when clarity is preferred over memory efficiency. It relies heavily on quick membership checks using a hash table while traversing the linked list.
Approach 2: Floyd's Cycle Detection Algorithm (O(n) time, O(1) space)
This method uses the classic tortoise and hare technique with two pointers. Move slow one step at a time and fast two steps at a time. If a cycle exists, the two pointers eventually meet inside the loop. Once they meet, reset one pointer to the head and move both pointers one step at a time. The node where they meet again is the start of the cycle. The mathematical insight is that the distance from head to cycle start equals the distance from meeting point to cycle start within the loop. This technique runs in O(n) time with O(1) space and avoids additional data structures. It is a classic application of two pointers combined with linked list traversal.
Recommended for interviews: Floyd's Cycle Detection Algorithm is the expected solution in most interviews. The hash table approach shows you understand cycle detection conceptually, but the two-pointer technique demonstrates deeper algorithmic reasoning and constant-space optimization. Interviewers often follow up by asking why resetting one pointer to the head works mathematically, so understanding the distance relationship inside the cycle is valuable.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Table | O(n) | O(n) | Simpler implementation when extra memory is acceptable |
| Floyd's Cycle Detection (Two Pointers) | O(n) | O(1) | Optimal interview solution when constant space is required |