Your question is Reverse Linked List or 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.
A Kraft Heinz product catalog pipeline represents an ordered feed as a singly linked list. Given the feed values and an optional cycle position, determine whether the list contains a cycle. If it is acyclic, reverse the linked list and return its values.
Use Floyd's tortoise-and-hare algorithm for cycle detection. Do not attempt to reverse a cyclic list because traversal would not terminate.
Implement reverse_if_acyclic(values, cycle_at), where values is a list of integers representing node values and cycle_at is either null or an integer index. If cycle_at is i, the final node points to the node at index i; otherwise, the final node points to null.
Return a dictionary with:
has_cycle: a Boolean indicating whether a cycle existsvalues: the reversed node values if the list is acyclic, or an empty list if it is cyclicThe input list must not be modified. Build the linked list from the supplied representation before applying the algorithm.
def reverse_if_acyclic(values, cycle_at):