FastPrepRemove a Cycle from a Singly Linked List
Problems/Remove a Cycle from a Singly Linked List

Remove a Cycle from a Singly Linked List

Morgan Stanley logoMorgan Stanley● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Morgan Stanley onsite interview for a full-time role. The author asks to detect and remove a cycle in a linked list, and links the standard task. Here the next pointers are an indexed array, so a real cycle is in the input and the changed link can be seen. The root is index 0. We chose the limits, what happens for empty input, and what the function returns.

Our version is about 90% the same as the reported question.

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 Apprenticeship and Tech Interviews: 6 Experiences

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)
See Morgan Stanley hiring insights
Saved
class Solution {
    public int[] removeListCycle(int[] nextIndex) {
        // Write your code here.
    }

}
Checking account…