Detect and Break a Linked-List Cycle
Learn this problem
AmazonNEW GRADONSITE INTERVIEWProblem statement
A singly linked list is represented by an integer array next. Node 0 is the head, and next[i] is either the index of node i's successor or -1 when it has no successor. Every node is reachable from the head.
If the list contains a cycle, find its entry node and then find the last node in that cycle, whose successor points back to the entry. Return a copy of next after changing that one offending successor to -1.
If the list has no cycle, return an unchanged copy. Use constant extra space apart from the returned array.
Function
breakLinkedListCycle(next: int[]) → int[]Examples
Example 1
next = [1,2,3,1]return = [1,2,3,-1]Nodes 1 -> 2 -> 3 -> 1 form a cycle. Node 3 is the last cycle node, so its successor is replaced with -1.
Example 2
next = [1,2,-1]return = [1,2,-1]The traversal reaches -1, so there is no cycle and the representation is unchanged.
Example 3
next = [0]return = [-1]The only node points to itself. It is both the cycle entry and the last node in the cycle, so its successor is removed.
Constraints
1 <= next.length <= 2 * 10^5.-1 <= next[i] < next.length.- Every node is reachable by starting at node
0and repeatedly following successors before a node repeats or-1is reached.