LinkedList Reverse Or Cycle | Dataford Interview Questions

Appzen may represent an audit chain as a linked list of event records. Given its pointer representation, determine whether following next references from the head eventually revisits a node.

Use Floyd's tortoise-and-hare algorithm. The linked list is encoded by an integer array next_indices, where node i points to next_indices[i]; -1 represents the end of the list. The head parameter is the starting node index, or -1 for an empty list.

Formal Specification

Implement has_cycle(next_indices, head). Return True if traversal from head enters a cycle, and False otherwise. Assume every non-negative pointer is a valid index in next_indices.

Constraints

0 <= len(next_indices) <= 10^5
head is -1 or a valid index
Each pointer is -1 or a valid index
The input array must not be modified
Use O(1) additional space

Function Signature

def has_cycle(next_indices, head):

Your question is LinkedList Reverse Or Cycle. 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