Linked List Cycle II
Medium
Given the head of a linked list, determine whether the linked list contains a cycle.
If a cycle exists, return the node where the cycle begins.
If there is no cycle, return null.
A cycle exists when a node's next pointer points to a previous node in the linked list.
Example 1
Input
head = [3, 2, 0, -4] pos = 1
Output
2
Explanation
The last node points back to the node containing 2.
Therefore, the cycle begins at node 2.
Example 2
Input
head = [1, 2] pos = 0
Output
1
Explanation
The last node points back to the first node.
Therefore, the cycle begins at node 1.
Constraints
0 <= n <= 10000
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked list.
The linked list may or may not contain a cycle.
Hints:
Hint 1
Use two pointers:
- slow moves one step at a time.
- fast moves two steps at a time.
Hint 2
If slow and fast meet, a cycle exists.
If fast reaches null, there is no cycle.
Auto
Loading editor...
Input
Expected Output