Linked List Head Or Cycle Detection | Dataford Interview Questions

A PlayStation Network navigation history is represented as a singly linked structure. Each item points to the index of the next item, or -1 when navigation ends. Given the current head index, determine whether the reachable structure contains a cycle and return the index where that cycle begins.

Use O(1) additional space. Do not modify the input.

Formal Specification

Implement detect_cycle(next_indices, head_index).

next_indices is a list of integers. For item i, next_indices[i] is the index of its next item, or -1.
head_index is the index of the current head, or -1 for an empty structure.
Return the index of the first node in the reachable cycle. Return -1 if no cycle exists.
Nodes that cannot be reached from head_index are irrelevant.

Constraints

0 <= len(next_indices) <= 10^5
Each pointer is -1 or a valid index in next_indices
head_index is -1 or a valid index in next_indices
The input structure is singly linked

Function Signature

def detect_cycle(next_indices, head_index):

Your question is Linked List Head Or Cycle Detection. 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