Linked List Cycle Detector
medium
Linked ListTwo PointersFast Slow PointersFloyd Cycle
Asked atAmazonMicrosoftGoogleMetaUber
Problem Description
Given the head of a linked list, determine whether the list contains a cycle. If it does, return the **node where the cycle begins**; otherwise return `null`.
A cycle exists when some node's `next` pointer points back to an earlier node in the list.
**Example 1:**
```
Input: head = [11, 3, 8, 6, 3], pos = 1
(node at index 1 is the tail's target)
Output: node with value 3 (index 1)
```
**Example 2:**
```
Input: head = [7, 14, 21], pos = -1
(no cycle)
Output: null
```
Constraints
- The number of nodes in the list is in the range [0, 10^4].
- -10^5 ≤ Node.val ≤ 10^5
- pos is -1 (no cycle) or a valid zero-based index into the list.
Follow-up
Can you determine the **length** of the cycle in O(n) time and O(1) space as well?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.