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}