Your question is Reverse List and Detect Cycles. 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.
AMD compiler and runtime components may represent dependency chains as singly linked lists. Given an indexed singly linked list, detect whether it contains a cycle and reverse it in place without allocating auxiliary memory.
Use Floyd's tortoise-and-hare algorithm to detect a cycle. If a cycle exists, leave the structure unchanged and report the cycle's entry index. If the list is acyclic, reverse every link in place.
Implement reverse_and_detect(values, next_indices, head), where values is an array of node payloads, next_indices[i] is the index of node i's successor, and -1 represents null. head is the starting node index. The function must return a dictionary with new_head, cycle_entry, and next_indices. Set cycle_entry to -1 for an acyclic list. The returned next_indices must reflect any in-place reversal.
Do not use sets, dictionaries for visited nodes, copied arrays, or recursion proportional to the list length.
def reverse_and_detect(values, next_indices, head):