Skip to content
RED SAGSkills
medium30 ptslinked-listtwo-pointersfloyd-cycle

Where Does the Cycle Begin?

A linked list is stored as an array of next pointers: next[i] is the index of the node after node i, or -1 if node i is the last one. You start at node head.

If following the pointers from head eventually loops, return the index of the first node of the loop (the node that is entered twice first). Otherwise return -1. Try to use constant extra memory.

Example 1

Input: next = [1,2,3,1], head = 0
Output: 1
Explanation: 0 -> 1 -> 2 -> 3 -> 1, so the loop starts at node 1.

Example 2

Input: next = [1,2,-1], head = 0
Output: -1

Constraints

  • 1 <= next.length <= 10^5
  • -1 <= next[i] < next.length
  • 0 <= head < next.length
Hint 1

Move a slow pointer one step and a fast pointer two steps; if they meet, there is a cycle.

Hint 2

After they meet, restart one pointer from head and move both one step at a time. They meet at the cycle entry.

Discussion 0

Join free to post in the discussion.

Good practice for: Backend Developer, Embedded Systems Engineer, Blockchain Developer, Site Reliability Engineer, Full Stack Developer

Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.