Find a Linked-List Cycle Entry
Updated
Problem statement
A singly linked list is represented by a table next. Row index i identifies node i, and next[i] is its next node ID. The value -1 means null.
Start at node 0. Return the ID of the node where its reachable cycle begins: the first node revisited during this traversal. Return -1 if traversal ends at null or the table is empty. Nodes outside the chain reachable from node 0 do not affect the answer.
Function
cycleEntry(next: int[]) → intExamples
Example 1
next = [1,2,3,1]return = 1Traversal is 0,1,2,3,1. Node 1 is the first repeated node, so it is the cycle entry.
Example 2
next = [1,2,0]return = 0Traversal returns to the head: 0,1,2,0. The cycle begins at node 0.
Example 3
next = [1,2,-1]return = -1Traversal 0,1,2 reaches null without repeating a node.
Constraints
0 <= next.length <= 20000.-1 <= next[i] <= 19999.- Every next entry is -1 or a valid index in the same table.
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
- Detect a Linked-List CyclePaytm · ONSITE INTERVIEWPaytm interview questions
- Detect a Linked-List CycleCapgemini · ONSITE INTERVIEWCapgemini interview questions
- Detect a Linked-List CycleMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- First Node Two Linked Lists ShareAdobe · PHONE SCREENAdobe interview questions
- Where Two Linked Lists MeetNutanix · PHONE SCREENNutanix interview questions
- Shortest Window with Required CountsOracle · ONSITE INTERVIEWOracle interview questions
- LRU CacheLotusFlare · ONSITE INTERVIEW
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Remove Nth Node From End of ListDruva · ONSITE INTERVIEW
- LRU CacheJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions