Cycle Detection in Doubly Linked List | Dataford Interview Questions

CareerBuilder's candidate profile navigation uses doubly linked structures. Given a serialized doubly linked list, determine whether any cycle is reachable from the head through either next or prev links. The structure may be malformed, so do not assume that prev links are exact reverses of next links.

Use Floyd's tortoise-and-hare algorithm rather than storing visited nodes, and do not modify the input.

Formal Specification

Implement has_cycle(next_links, prev_links, head), where next_links and prev_links are arrays of equal length. Each array entry is either an integer node index or None. head is an integer index or None. Return True if repeatedly following next from head eventually repeats a node, or if repeatedly following prev from head eventually repeats a node. Otherwise, return False.

Constraints

0 <= len(next_links) <= 10^6
len(next_links) == len(prev_links)
head is None or a valid node index
Every non-None link is a valid node index
The input is not modified

Function Signature

def has_cycle(next_links, prev_links, head):

Your question is Cycle Detection in Doubly Linked List. 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