Detect and Break a Linked-List Cycle
Updated
Problem 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.
More Amazon Onsite Interview questions
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Dungeon GameONSITE INTERVIEW · Seen Nov 2026
- Integer BreakONSITE INTERVIEW · Seen Nov 2026
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
- First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Unique Target-Sum Pairs in a Sorted Doubly Linked ListArista Networks · PHONE SCREENArista Networks interview questions
- Search a Row- and Column-Sorted MatrixByteDance · ONSITE INTERVIEWByteDance interview questions
- Shortest Window with Required CountsOracle · ONSITE INTERVIEWOracle interview questions
- 3Sum SmallerSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Sort Ones, Twos, and Threes In PlaceAgoda · PHONE SCREEN · ONSITE INTERVIEWAgoda interview questions
- Remove Nth Node From End of ListDruva · ONSITE INTERVIEW
- Minimum Station Tracks for a Train ScheduleBNSF Railway · ONSITE INTERVIEWBNSF Railway interview questions
- Candy Crush Grid Matching and GravityRoblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
- Longest Binary Window with at Most K OnesLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Find the Entry of a Linked List CycleQualys · ONSITE INTERVIEWQualys interview questions