#142
Linked List Cycle II
specialist · 755 · lc medium +31 · verified · 57.3% accepted · 15,082 likes · top 53%
Description
Given the head of a linked list, find and return the node where the cycle begins. If no cycle exists, return null.
A cycle exists when some node can be revisited by following next pointers. The variable pos (0-indexed, not passed as input) marks where the tail reconnects; it is -1 if there is no cycle.
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.
Code
1
2
3
4
5
6
7
8
9