Create Linked List and Detect Cycles | Dataford Interview Questions

The Gap app receives a sequence of product record IDs that must be represented as a singly linked list. Implement the list construction and determine whether the resulting list contains a cycle.

A cycle is created when the final node points back to an earlier node. The input identifies that earlier node by its zero-based index. Use Floyd's tortoise-and-hare algorithm for cycle detection, do not use a set or dictionary of visited nodes, and do not modify node links after construction.

Formal Specification

Implement has_cycle(values, cycle_index). values is a list of integers used to create one node per value. cycle_index is an integer: -1 means the final node points to None; otherwise, the final node must point to the node at that zero-based index. Return True if the constructed list contains a cycle, and False otherwise.

Constraints

0 <= len(values) <= 100000
-10^9 <= values[i] <= 10^9
cycle_index is -1 or a valid index in values
The linked list must be constructed from custom nodes
The cycle detection phase must use O(1) auxiliary space

Function Signature

def has_cycle(values, cycle_index):

Your question is Create Linked List and Detect Cycles. 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