Remove a Cycle from a Singly Linked List
Updated
Problem statement
Remove a cycle from a singly linked list if one exists, preserving every node and its original first-visit order. For this exercise, node i is represented by array entry nextIndex[i]: its value is the index of the next node, or -1 for a null next pointer. A nonempty list starts at head index 0.
Every represented node is reached from that head before the first null or repeated node. Thus the input is either one linear list or a prefix followed by a cycle. The input array can contain a genuine back-link; node indices need not be in traversal order.
If a cycle exists, set only its predecessor-of-entry link to -1: this is the link from the last first-visited node back into the cycle. Keep every other link unchanged. If no cycle exists, change nothing. Update the supplied next-pointer array in place and return its updated entries as an observation of that mutation. An empty list returns an empty array.
Aim for O(n) time and O(1) working space, excluding the returned observation. Returning the input unchanged cannot handle cyclic cases; cutting a link that loses nodes is also incorrect.
Function
removeListCycle(nextIndex: int[]) → int[]Examples
Example 1
nextIndex = [1,2,3,4,2]return = [1,2,3,4,-1]The first-visit order is 0→1→2→3→4, then node 4 points back to node 2. Cutting only nextIndex[4] to -1 yields [1,2,3,4,-1] and retains all five nodes.
Example 2
nextIndex = [3,2,4,2,1]return = [3,-1,4,2,1]The first-visit order is 0→3→2→4→1, then node 1 points back to node 2. The correct cut is nextIndex[1], giving [3,-1,4,2,1]. Cutting the last array slot would lose nodes and change the wrong link.
Constraints
- For this exercise, assume 0 <= nextIndex.length <= 500.
- Every next index is between -1 and 499, inclusive.
- For nonempty input, every nonnegative next index is less than nextIndex.length, and all represented nodes are encountered from head index 0 before the first null pointer or repeated node.
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)
- Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)