Linked List Loop Detection | Dataford Interview Questions

A runtime component at HashedIn by Deloitte receives linked lists representing processing chains. Determine whether the chain eventually loops back to a previously visited node.

Implement contains_loop(nodes, head) using constant auxiliary space.

Formal Specification

nodes is a list where each element has the form [value, next_index].
value is an integer payload and next_index is the zero-based index of the next node.
A next_index of -1 represents the end of the list.
head is the index of the first node, or -1 for an empty list.
Return True if the nodes reachable from head contain a cycle. Otherwise, return False.
Nodes not reachable from head must not affect the result.

Constraints

0 <= len(nodes) <= 10^5
-10^9 <= value <= 10^9
Each next_index is -1 or a valid index in nodes
Only nodes reachable from head are relevant

Function Signature

def contains_loop(nodes, head):

Your question is Linked List Loop 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