Cycle Detection in Linked List

EasyPython

Problem

A Capgemini Engineering service represents a singly linked list using an array of next-pointer indices. Given this representation, determine whether traversing from a specified head node eventually revisits a node.

Implement has_cycle(next_index, head). next_index[i] is the index of the node reached from node i, or -1 if the node has no successor. The list may contain nodes that are unreachable from head; ignore them. Return True if the reachable portion contains a cycle, otherwise return False.

Use O(1) auxiliary space. Do not modify the input. An optimal solution should run in linear time relative to the number of reachable nodes.

Formal Specification

Input: next_index, a list of integers, and head, an integer node index.
Output: a Boolean indicating whether the list reachable from head contains a cycle.
Node indices are zero-based. -1 represents the null pointer.

Constraints

0 <= len(next_index) <= 10^6
head is -1 or a valid index in next_index
Each next pointer is -1 or a valid index in next_index
The input must not be modified

Function Signature

def has_cycle(next_index, head):

Use O(1) auxiliary space. Do not modify the input. An optimal solution should run in linear time relative to the number of reachable nodes.

Formal Specification

Input: next_index, a list of integers, and head, an integer node index.
Output: a Boolean indicating whether the list reachable from head contains a cycle.
Node indices are zero-based. -1 represents the null pointer.