Find a Linked-List Cycle Entrance

Interview Problem Interview Medium Fast and Slow Pointers Array Linked List

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.detectCycle(nextIndices). Index 0 is head; nextIndices[i] is the next node index or None. Return the cycle entrance index, or -1 when acyclic. This serializable contract preserves the original pointer graph.

Starter code

class Solution:
    def detectCycle(self, nextIndices):
        pass

Test cases

entry-one

{
  "args": [
    [
      1,
      2,
      3,
      1
    ]
  ]
}

Expected: 1

Wizard outline

Step 1: Initialize Solution.detectCycle
Replace the empty starter with the first real state owned by Solution.detectCycle. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Acyclic case
Complete the readable core algorithm for one representative Interview case. Find a fast-slow meeting, reset one pointer to head, and advance equally to the entrance.
Step 4: Harden the Entry One boundary
Repair the reviewed boundary and pass the complete submission contract. Different speeds meet iff the reachable path contains a cycle. Floyd's distance relation guarantees that after resetting one pointer to head, equal-speed pointers next meet exactly at the cycle entrance.

Footguns and prerequisites

The first meeting inside a cycle is not necessarily the cycle entrance.
linked lists

Reviewed references

LeetCode 142 — Linked List Cycle II

Practice prerequisites

Trace Fast and Slow Pointers(opens in a new tab)
Trace Fast and Slow Pointers isolates after each loop, slow has advanced one link for every two links attempted by fast. That focused state discipline is required when implementing linked cycle entry index as a complete Interview Problem.

Recommended approach and implementation

Advance slow once and fast twice through nextIndices until they meet or fast reaches None. Reset finder to head and advance it with slow one step until equal.

Why it works: Different speeds meet iff the reachable path contains a cycle. Floyd's distance relation guarantees that after resetting one pointer to head, equal-speed pointers next meet exactly at the cycle entrance.

class Solution:
    def detectCycle(self, nextIndices):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        if not nextIndices: return -1
        slow = fast = 0
        while fast is not None and nextIndices[fast] is not None:
            slow = nextIndices[slow]
            fast = nextIndices[nextIndices[fast]]
            if slow == fast:
                finder = 0
                while finder != slow:
                    finder = nextIndices[finder]
                    slow = nextIndices[slow]
                return finder
        return -1

Similar exercises

Find the Duplicate Number(opens in a new tab)