Insert a Value into a Sorted Circular Linked List
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
## Problem
A sorted circular singly linked list is encoded as an array `cycleValues` in the
order encountered while traversing once from the supplied head. The implicit
last node points back to index zero, and the supplied head may be anywhere in
the sorted cycle rather than at its minimum. Insert `insertValue` while
preserving circular sorted order. Return the canonical value-array encoding of
the result: start at a minimum value and traverse once, so the returned array is
nondecreasing. An empty input represents an empty cycle.
### Constraints & Assumptions
- `0 <= len(cycleValues) <= 100,000`.
- Every array value and `insertValue` is a 32-bit signed integer.
- For nonempty input, the cyclic order is valid: there is at most one index `i` with `cycleValues[i] > cycleValues[(i + 1) % n]`.
- The list may contain duplicates or consist entirely of one repeated value.
- Use `O(n)` time and `O(1)` auxiliary space excluding the returned array.
### Clarifications
- The function accepts only JSON-portable arrays and integers; no custom node type appears in the public API.
- The output contains every input occurrence plus exactly one occurrence of `insertValue`.
- Although several physical insertion positions may be equivalent among equal values, canonical nondecreasing output makes the graded result unique.
- For empty input, return `[insertValue]`.
### Examples
```text
cycleValues = [3, 4, 1]
insertValue = 2
output = [1, 2, 3, 4]
cycleValues = [2, 2, 2]
insertValue = 2
output = [2, 2, 2, 2]
```
### Hints
```hint Separate ordinary and wraparound edges
An insertion may fit between two increasing neighbors or across the maximum-to-minimum boundary.
```
```hint Canonicalize the traversal
After insertion, identify a minimum position and emit exactly one full cycle from there.
```
Overview: Insert an integer into a sorted circular singly linked list whose supplied head may not be the minimum. Preserve duplicates and the single wrap point, then return a canonical nondecreasing traversal beginning at a minimum value.
Read the full Meta Software Engineer interview experience this question came from
A sorted circular singly linked list is encoded by cycleValues in the order seen during one traversal from the supplied head. The implicit last node points to index zero, and the head may be anywhere in the sorted cycle. Insert insertValue while preserving circular sorted order, then return the unique canonical array encoding: begin at a minimum value and traverse once, so the result is nondecreasing. The empty array represents an empty cycle.
Constraints
- 0 <= len(cycleValues) <= 100000.
- Every array value and insertValue is a signed 32-bit integer.
- A nonempty input has at most one cyclic descent cycleValues[i] > cycleValues[(i + 1) % n].
- The cycle may contain duplicates or one repeated value only.
- The output contains every original occurrence plus exactly one insertValue.
- An empty input returns [insertValue].
Examples
Input: ([3, 4, 1], 2)
Expected Output: [1, 2, 3, 4]
Explanation: This is the first source example; the supplied head lies after the minimum.
Input: ([2, 2, 2], 2)
Expected Output: [2, 2, 2, 2]
Explanation: This is the second source example; equal physical insertion positions share one canonical output.
Hints
- The minimum occurs immediately after the cycle's strict maximum-to-minimum descent.
- Once traversal begins at a minimum, insert into the resulting nondecreasing order.