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

Expedia logoExpedia● MediumNEW GRADINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report leaves out number limits. The goal of removing the cycle matches the report at about 95%.

Remove a cycle from a singly linked list, preserving the original first-visit order of all nodes reachable from its head.

For this exercise, node i points to nextIndex[i], or to null when that entry is -1. A nonempty list starts at node 0. Indices need not follow traversal order. Nodes not reachable from the head are ignored and their entries must remain unchanged.

If the reachable list contains a cycle, change only the link from the last first-visited node back to the cycle entry: set that entry to -1. Otherwise change nothing. Mutate the array and return its updated contents. An empty array returns an empty array.

Aim for O(n) time and O(1) working space, excluding the returned observation.

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

  • 0 <= nextIndex.length <= 500.
  • Every next index is between -1 and 499, inclusive.
  • Every nonnegative next index is less than nextIndex.length.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Remove Nth Node From End of ListDruva · ONSITE INTERVIEW
  • Find the Entry of a Linked List CycleQualys · ONSITE INTERVIEWQualys interview questions
  • Detect a Linked-List CyclePaytm · ONSITE INTERVIEWPaytm interview questions
  • Detect a Linked-List CycleCapgemini · ONSITE INTERVIEWCapgemini interview questions
  • Rearrange a Linked List from Alternating EndsConcentric AI · ONSITE INTERVIEWConcentric AI interview questions
  • Palindrome Linked List with RestorationMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Linked List Cycle Entry NodeGoogle · ONSITE INTERVIEWGoogle interview questions
  • Detect and Break a Linked-List CycleAmazon · ONSITE INTERVIEW
  • Odd-Even Linked ListBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
  • Find the Entry of a Linked List CyclePeopleStrong · ONSITE INTERVIEWPeopleStrong interview questions

Interview reports that mention this question

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia New Grad SDE Earlier Loops: 5 Experiences (Part 2 of 3)

Expedia interview experiences

  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int[] removeListCycle(int[] nextIndex) {
        // Write your code here.
    }

}
Checking account…