Solution: Insert into a Sorted Circular Linked List

Statement

You’re given a reference to a node, head, in a circular linked list, where the values are sorted in non-decreasing order. The list is circular, so the last node points to the first node. However, the head can be any node in the list—it is not guaranteed to be the node with the smallest value.

Your task is to insert a new value, insertVal, into the list so that it remains sorted and circular after the insertion.

• You can choose any of the multiple valid spots where the value can be inserted while maintaining the sort order.

• If the list is empty (i.e., the given node is NULL), create a new circular list with a single node containing insertVal, and return that node.

• Otherwise, return the head node after insertion.

Constraints:

• The number of nodes in the list is in the range $[0, 10^3]$.

• $-10^3 \leq$ Node.val, insertVal $\leq 10^3$

Solution

The intuition behind this solution is to perform an in-place insertion into a sorted circular linked list while preserving its structure and order. The tricky part is that the list is sorted and circular, but the head can point to any node, not just the smallest one. So, we can’t just move in one direction and expect the values to increase. Instead, we iterate through the list by moving two pointers: one for the current node and one for the previous node. In each iteration, we check if the value to be inserted fits between the previous and current pointers. If it does, we insert the value between the previous and current pointers. Otherwise, we move both pointers one step ahead to keep iterating and finding the right position to insert the value. If we traverse the entire list and return to the starting point without finding a suitable spot, no ideal position was found. This can happen when all nodes have the same value or the value doesn’t fit between any two nodes. In such cases, the value can be inserted anywhere in the list. So, we simply insert it after completing the loop.

Let’s dive deeper into the above intuition:

This problem looks simple at first, but has some hidden complexity. Because the list is circular and sorted, there’s no clear start or end. So we need a smart way to find the right place for the new value.

We use two pointers—prev and curr—to move through the list and look at each pair of nodes. There are three main situations we need to handle:

Case 1: Insert between two nodes in a sorted order

If the value to insert is greater than or equal to prev.val and less than or equal to curr.val, it fits right in between. This is the usual sorted case. We insert the new node between prev and curr.