Linked List Cycle II
Medium
Given the head of a linked list, determine if the linked list has a cycle.
If a cycle exists, return the node where the cycle begins.
If there is no cycle, return null.
A cycle exists if there is some node in the list that can be reached again by continuously following the next pointer.
Example 1
Input
n = 4 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
n = 2 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.
Do not modify the linked list.
Hints:
Hint 1
Use two pointers:
slow
fast
Move:
slow → one step
fast → two steps
Hint 2
If a cycle exists, slow and fast will eventually meet.
If fast reaches null, there is no cycle.
Auto
Loading editor...
Input
Expected Output