Reverse List or Detect Cycle | Dataford Interview Questions

Your question is Reverse List or Detect Cycle. 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.

Problem

Amazon Development Center U.S. services may process linked sequences of event records. Given a singly linked list, determine whether it contains a cycle. If it is acyclic, reverse it in place and return the resulting links.

The list is represented by two arrays: values, where values[i] is the value stored at node i, and next_indices, where next_indices[i] is the index of the next node or -1 for the terminal node. Node 0 is the head. Do not allocate a second list of nodes.

Return a dictionary with has_cycle. For a cyclic input, set next_indices to None and leave the structure unchanged. For an acyclic input, set has_cycle to False and return the reversed links in next_indices. The returned links must use the same node indices, with the original tail becoming the new head. Also return head, the index of the new head, or -1 for an empty list.

Constraints

0 <= len(values) == len(next_indices) <= 10^5
Each next index is -1 or an integer from 0 through len(values) - 1
The head is node 0 when the list is non-empty
A cyclic list must not be reversed

Function Signature

def reverse_or_detect(values, next_indices):

Your question is Reverse List or Detect Cycle. 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.

Constraints

0 <= len(values) == len(next_indices) <= 10^5
Each next index is -1 or an integer from 0 through len(values) - 1
The head is node 0 when the list is non-empty
A cyclic list must not be reversed

Function Signature

def reverse_or_detect(values, next_indices):