471. Insert into a Sorted Circular Linked List
You're handed head, a reference to some node of a circular linked list whose values are sorted in non-decreasing order — but head is not necessarily the smallest element, so the ascending run may "wrap around" the circle at one seam where the largest value points back to the smallest. Each node is a Node with an integer val and a next pointer; in a circular list the last node's next points back around, so following next forever loops through every node.
Write a function insert(head, insertVal) that splices a new node holding insertVal into the circle so the list is still sorted-circular, and returns a reference to any node of the resulting list. Two special cases matter:
headmay be null (an empty list). Create a single node whosenextpoints to itself and return it.- If several positions are valid (duplicates, or a circle where every value is equal), any of them is accepted.
The grader checks the circle by reading it from its smallest point, so what must hold is the shape: exactly one new node, all old nodes still reachable, and some rotation of the circle non-decreasing.
Example 1:
Input: insert(head = [3, 4, 1] (circular), insertVal = 2)
Output: the circle 3 → 4 → 1 → 2 → (3), read from smallest: [1, 2, 3, 4]
Explanation: The circle is 3 → 4 → 1 → back to 3; the seam is 4 → 1. The value 2 belongs between 1 and 3, so the new node is spliced there. Read from its smallest point the circle is 1, 2, 3, 4.
Example 2:
Input: insert(head = null, insertVal = 1)
Output: a single self-pointing node: [1]
Explanation: The list is empty, so insert must build the one-node circle: a node holding 1 whose next points to itself, returned as the new reference.
Constraints:
- 0 ≤ number of nodes ≤ 5 * 10⁴
- -10⁶ ≤ Node.val, insertVal ≤ 10⁶
- The input circle is sorted non-decreasing up to rotation (one seam at most)
Hints:
Walk the circle with a pair of neighbors (prev, cur). In a normal ascending stretch, insertVal fits when prev.val <= insertVal <= cur.val.
There is exactly one seam — the place where prev.val > cur.val (largest wraps to smallest). A new maximum or new minimum both belong there: insertVal >= prev.val or insertVal <= cur.val.
If you complete a full lap without either condition firing, every value in the circle is equal — insert anywhere. Without this lap guard, an all-equal circle plus a different insertVal loops forever.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [3, 4, 1] (circular), insertVal = 2
Expected output: circle from smallest: [1, 2, 3, 4]