Skip to content
CodeKruPro

Detect a loop in a chain of links and find where it starts

Coding problemMediumAsked in: Adobe, Amazon, Apple, Google, Meta, Microsoft

A chain of nodes is described by a list links. The nodes are numbered from 0, and links[i] is the number of the node that comes after node i, or -1 when node i has no next node. This is how a linked list looks in memory.

Start at node 0 and keep following links. Either you reach a node with no next node, or you go round a loop forever. Return -1 if there is no loop. Otherwise return the number of the first node of the loop: the first node you would visit twice.

Some nodes may never be reached from node 0; they do not matter. Try to use only a constant amount of extra memory.

Examples

Example 1
Input: links = [1,2,3,1]
Output: 1
The walk is 0, 1, 2, 3, then back to 1. Node 1 is the first node seen twice.
Example 2
Input: links = [1,2,-1]
Output: -1
The walk 0, 1, 2 ends.
Example 3
Input: links = [0]
Output: 0
Node 0 links to itself.

Constraints

  • The list holds between 1 and 100,000 links
  • Each link is -1 or a node number between 0 and n - 1

Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.

Run your code to see the results here.

This question is part of Pro+

Pro+ opens every question in Interview Prep and the mock interview. Every article and the first 2 questions of each topic stay free. Hands-on Selenium and API tasks follow their course lesson's own lock.

See Pro+

Already have Pro+? Sign in