Linked Lists Fast and slow pointers
289. Linked List Cycle
You are given head, the first node of a singly linked list. Return true if the list has a loop, and
false if it does not.
A list has a loop (also called a cycle) when a walk along the next pointers from the head never reaches
null. The walk comes back to a node it has already passed and then goes round the same nodes forever. The loop
does not have to include the head. In the list below, the last node points back to the second node, so the
walk goes round 8, -2, 5 and 8 forever:
The examples write a list as its values from the head on, so head = [4,1,6] is the list 4 → 1 → 6. The
second input, pos, says how the loop is closed: the last node's next points to the node at index pos,
counting from 0 at the head. pos = -1 means the last node's next is null. Your function gets only head;
it never sees pos.
Example 1
Input: head = [3, 8, -2, 5, 8], pos = 1
trueExplanation: This is the list in the picture. The last node points back to node 1, so a walk from the head passes 3 and then goes round the four nodes holding 8, -2, 5 and 8 forever.
Example 2
Input: head = [4, 4, 4], pos = -1
falseExplanation: All three nodes hold 4, but they are three different nodes. The last node's next is null, so the walk
ends after three nodes and the list has no loop.
Example 3
Input: head = [-6], pos = 0
trueExplanation: The only node's next points to the node itself. A single node can make a loop on its own.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109-1 ≤ pos ≤ 105 − 1- A
posoutside0 … n − 1, where n is the number of nodes, means the list has no loop.
Clarifying questions
What you would ask an interviewer before writing any code.