Detect a Loop in Linked List

EasyPython

Problem

Amazon Lab126 diagnostics can represent Fire TV playback events as a singly linked list. Given an index-based representation of that list, determine whether following next pointers eventually revisits a node.

Use Floyd's cycle detection algorithm with a slow pointer moving one step at a time and a fast pointer moving two steps at a time. Do not use a visited set for the primary solution.

Formal Specification

Implement has_cycle(values, next_indices), where values is an array containing node payloads and next_indices[i] is the index of the node reached from node i. A value of -1 means that node i has no successor. The arrays describe nodes indexed from 0; an empty list represents an empty linked list whose head is absent. The head is always node 0 when at least one node exists.

Return True if traversal from node 0 enters a cycle, otherwise return False.

Constraints

0 <= len(values) <= 10^5
len(next_indices) == len(values)
Each next index is -1 or a valid node index
The head is node 0 when the list is nonempty

Function Signature

def has_cycle(values, next_indices):

Use Floyd's cycle detection algorithm with a slow pointer moving one step at a time and a fast pointer moving two steps at a time. Do not use a visited set for the primary solution.

Formal Specification

Return True if traversal from node 0 enters a cycle, otherwise return False.