Find the Entry of a Linked List Cycle
Updated
Problem statement
Find the entry node of the cycle reachable from a singly linked list's head. The entry is the first node you would visit twice when following the links from the head. Return -1 if no cycle is reachable.
For this exercise, links are encoded by an array next. Node IDs are the array indices, starting at 0. next[i] is the ID of the node after node i, or -1 if there is no next node. For a nonempty array, node 0 is the head. An empty array represents an empty list. Ignore any nodes unreachable from the head.
Return the entry node's ID, rather than its position in the traversal. Aim for O(n) time and O(1) auxiliary space.
Function
findCycleEntry(next: int[]) → intExamples
Example 1
next = [1,2,3,1]return = 1The traversal 0 → 1 → 2 → 3 → 1 first repeats node 1, so that node is the cycle entry.
Example 2
next = [1,-1]return = -1The traversal terminates after nodes 0 and 1, so there is no reachable cycle.
Constraints
- For this exercise, assume
0 <= next.length <= 10^5. - Each entry is
-1or a valid ID smaller thannext.length.
More PeopleStrong Onsite Interview questions
- Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
- Four SumONSITE INTERVIEW · Seen Mar 2026
- LRU Cache OperationsONSITE INTERVIEW · Seen Mar 2026
- Sliding Window MaximumONSITE INTERVIEW · Seen Mar 2026
- Integer to English Words: Up to 20 DigitsONSITE INTERVIEW · Seen Sep 2025
- Word Ladder II: All Shortest TransformationsONSITE INTERVIEW · Seen Sep 2025
- Detect a Cycle in a Linked ListONSITE INTERVIEW · Seen May 2025
- First Nonrepeating CharacterONSITE INTERVIEW · Seen May 2025
- Longest Subarray with a Target SumONSITE INTERVIEW · Seen May 2025
- Lowest Common Ancestor in a BSTONSITE INTERVIEW · Seen May 2025
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
- Remove a Cycle from a Singly Linked ListExpedia · ONSITE INTERVIEWExpedia interview questions