To solve Linked List Cycle II, immediately check if the list is empty or has a single node. Use two pointers moving at different speeds to detect a cycle, then reset one pointer to head to find the cycle's start. This approach leverages the linked-list pointer manipulation pattern while minimizing extra space and handling null edge cases carefully.
Problem Statement
Given the head of a singly linked list, determine if the list contains a cycle. If a cycle exists, return the node where the cycle begins; otherwise, return null. The linked list must not be altered, and cycle detection should consider all nodes reachable through the next pointer.
A cycle occurs if following next pointers eventually revisits a previous node. Internally, pos indicates the index of the node connected by the tail (0-indexed) or -1 if no cycle exists. You must implement an efficient approach using either a hash table or two-pointer strategy without changing node connections.
Examples
Example 1
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
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
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
There is no cycle in the linked list.
Constraints
- The number of the nodes in the list is in the range [0, 104].
- -105 <= Node.val <= 105
- pos is -1 or a valid index in the linked-list.
Solution Approach
Hash Table Approach
Traverse the list while storing each visited node in a hash set. If a node is revisited, that node is the cycle's start. This approach guarantees O(n) time and O(n) space but explicitly tracks every node to prevent infinite loops.
Two-Pointer (Floyd's Tortoise and Hare) Approach
Use a slow pointer moving one step and a fast pointer moving two steps. If they meet, a cycle exists. Reset one pointer to head and move both one step at a time; their meeting point is the cycle's starting node. This method provides O(n) time and O(1) space, leveraging linked-list pointer manipulation.
Edge Case Handling
Always check for empty lists or lists with a single node, as these cannot form a cycle. Ensure that pointer resets and movements avoid null references. Careful implementation avoids infinite loops or misidentifying the cycle start.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) for both hash table and two-pointer approaches, scanning each node at most twice. Space is O(n) for the hash table method and O(1) for two-pointer technique. Pointer resets and step calculations dominate runtime, especially when the cycle starts near the head.
What Interviewers Usually Probe
- Candidate recognizes pointer manipulation and cycle detection pattern immediately.
- Candidate distinguishes between detecting a cycle and locating its start.
- Candidate considers edge cases with null or single-node lists and avoids modifying the original list.
Common Pitfalls or Variants
Common pitfalls
- Misidentifying the meeting point of fast and slow pointers as the cycle start.
- Failing to handle empty lists or single-node lists, causing null pointer errors.
- Using extra space unnecessarily when two-pointer solution suffices.
Follow-up variants
- Return the cycle length instead of the starting node.
- Detect multiple cycles in a list with added constraints.
- Modify the list to mark visited nodes and detect the cycle, trading safety for space.
How GhostInterview Helps
- Provides step-by-step guidance to implement two-pointer cycle detection safely.
- Highlights common mistakes in pointer handling specific to Linked List Cycle II.
- Offers optimized solutions with O(1) space and clear identification of cycle entry points.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the fastest approach for Linked List Cycle II?
The two-pointer method (Floyd's Tortoise and Hare) efficiently finds the cycle start with O(n) time and O(1) space.
Can we use a hash table to solve Linked List Cycle II?
Yes, storing visited nodes in a hash set allows detecting the cycle start but requires O(n) extra space.
How do we handle lists with no cycle?
Return null immediately after traversing without revisiting any node; two-pointer or hash table methods both handle this.
Does the problem allow modifying the linked list?
No, the list must remain unaltered to maintain pointer integrity for cycle detection.
Why is pointer manipulation important in Linked List Cycle II?
Correct pointer manipulation ensures detection of the cycle start without extra space, preventing infinite loops and null errors.
Need direct help with Linked List Cycle II instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Linked List Cycle II from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine if a given linked list contains a cycle using pointer manipulation or hashing, focusing on detecting repeated nodes efficiently.
Open problem page#160 Intersection of Two Linked ListsGiven two linked lists, find the node where they intersect or return null if they do not.
Open problem page#143 Reorder ListReorder List requires careful pointer manipulation in a singly linked list to interleave nodes from the ends without altering values.
Open problem page