DSA problem
Insert into a Sorted Circular Linked List
You are given a node from a circular linked list that is sorted in non-decreasing order. The given node can be any node in the list, not necessarily the smallest. You must insert a new node with a given value into the list such that the list remains sorted and circular, and then return a reference to any node in the resulting list.
If the list is empty (the given node is null), you create a one-node circular list whose single node points to itself. Otherwise, you walk the circle looking for an adjacent pair of nodes between which the new value belongs.
There are three cases to handle while traversing. The simplest is when the new value fits between a node and its successor (cur.val <= insertVal <= cur.next.val). The second is the "wrap-around" point, where the list value drops from its maximum back to its minimum; the new value should be inserted here if it is greater than or equal to the maximum or less than or equal to the minimum. The third case is when the entire list has equal values, in which case you go all the way around and insert anywhere.
The optimal approach is a single traversal around the circle starting from the given node. At each step, check the three insertion conditions, and if none match, advance. If you return to the starting node without finding a spot (a uniform-value list), insert before the start. This runs in O(n) time and O(1) extra space.
Examples
head = [3,4,1], insertVal = 2[3,4,1,2]head = [], insertVal = 1[1]head = [1], insertVal = 0[1,0]Constraints
- The number of nodes in the list is in the range [0, 5 * 10^4].
- -10^6 <= Node.val, insertVal <= 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.