Your question is Linked List and Graph/Tree Coding. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Synopsys Design Compiler can represent a simplified module dependency chain as nodes with at most one outgoing dependency. Given this structure, determine whether following dependencies from a specified node eventually revisits a node.
Implement the solution using linked-list pointer techniques. Then provide an alternative graph-based solution that detects the same cycle using traversal state.
The input contains an integer array next_nodes and an integer head. Node i points to next_nodes[i]. A value of -1 means that the node has no outgoing dependency. Return True if traversal from head revisits a node, otherwise return False.
The linked-list solution should use O(1) auxiliary space with the slow and fast pointer technique. The graph solution may use additional traversal state.
def has_cycle_linked_list(next_nodes, head):