Find the First Node of a Loop in a Linked List
Implement findLoopStartIndex
Given the
head of a singly linked list that may contain a cycle, return the 0-indexed position of the node where the cycle begins, or -1 if there is no cycle.
Since node values may repeat, the answer has to be a position, not a value — otherwise an earlier duplicate could be mistaken for the loop's actual start. The optimal solution runs Floyd's Cycle DetectionFloyd's Cycle DetectionThe "tortoise and hare" algorithm: slow and fast pointers moving at 1 and 2 steps per iteration. Once they meet inside a cycle, resetting one pointer to head and advancing both at equal speed makes them meet again exactly at the cycle's first node — a property that follows from the arithmetic of how far each pointer traveled to reach the meeting point. in two phases: first find where slow and fast meet, then reset one pointer to head and walk both one step at a time until they meet again — that second meeting point is the loop's start.
Example 1:
Input: head = {"vals":[3,2,0,-4],"pos":1}
Output: 1
Example 2:
Input: head = {"vals":[1,2],"pos":0}
Output: 0
Example 3:
Input: head = {"vals":[1],"pos":-1}
Output: -1
+ 5 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes in head ≤ 10⁴ - ●
-10⁹ ≤ node value ≤ 10⁹ - ●
A cyclic test list is described as (vals, pos) — the last node's next points back to index pos (0-indexed); pos = -1 means no cycle - ●
The answer is the 0-indexed position of the loop's first node, or -1 if there is no loop — a position, not a value, since values may repeat
head =
{"vals":[3,2,0,-4],"pos":1}