Linked Lists Fast and slow pointers
293. Linked List Cycle II
You are given head, the first node of a singly linked list. The list may have a cycle: the last node's
next, instead of being null, may point back to an earlier node or to the last node itself. Return the node
where the cycle starts, or null if the list has no cycle. Do not change the list.
The start of the cycle is the first node you reach a second time when you follow next from the head.
Every node from there on is part of the cycle, and the nodes before it are not.
The examples write a list as its values from the head on, plus pos, the index (from 0) of the node that the
last node links back to. pos = -1 means the last node's next is null. Your function gets only head;
pos only describes the list. So head = [8,6,1,4], pos = 1 is this list:
The output shows the node you return as its index in the list, counted from 0 at the head, and shows null as
-1. Values can repeat, so two nodes with the same value are still different nodes.
Example 1
Input: head = [3, 5, 9, 5, 7], pos = 1
1Explanation: The last node, holding 7, links back to the node at index 1. Following next from the head visits 3, 5,
9, 5, 7 and then reaches the node at index 1 again. The node at index 3 also holds 5, but it is a
different node, and it is not reached twice first.
Example 2
Input: head = [-2, -2, -2], pos = 0
0Explanation: The last node links back to the head, so the whole list is the cycle and it starts at index 0. All three nodes hold -2; only the position tells them apart.
Example 3
Input: head = [10, 20, 30], pos = -1
-1Explanation: The last node's next is null, so the list has no cycle and the answer is null, shown as -1.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109-1 ≤ pos ≤ 105 − 1posis-1(no cycle) or the index of a node. Apospast the last node also means no cycle.
Clarifying questions
What you would ask an interviewer before writing any code.