Linked List Cycle Algorithm | Dataford Interview Questions

A Panasonic connected-device component stores its processing path as a singly linked list. A faulty update may cause one node to point back to an earlier node, creating an infinite traversal cycle.

Given an array next_indices and a starting node index head, determine whether the linked list contains a cycle. If it does, return the index of the node where the cycle begins. Otherwise, return -1.

Formal Specification

next_indices is a list of integers. Node i points to next_indices[i].
A value of -1 represents a null pointer.
head is the index of the first node, or -1 for an empty list.
Return the index of the cycle's entry node, or -1 when no cycle exists.
Do not modify next_indices.
Solve the problem with constant auxiliary space.

Constraints

0 <= len(next_indices) <= 10^6
Each pointer is -1 or a valid index in next_indices
head is -1 or a valid index in next_indices
Only nodes reachable from head affect the result
The input array must not be modified

Function Signature

def detect_cycle(next_indices, head):

Your question is Linked List Cycle Algorithm. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem