Insert into a Sorted Circular Linked List

Problem Statement

In this task, we are dealing with a Circular Linked List that is sorted in non-descending order (i.e., the next node's value is either equal to or greater than the current node's value, and this wraps around at the end of the list). Our objective is to insert a new value, insertVal, into this circular list such that the list maintains its sorted order.

The complexity arises from several properties of circular linked lists:

• The starting point in the provided list may not be the smallest element.
• The list can loop indefinitely, which requires careful handling to avoid infinite loops.
• Handling insertions when the list is empty (node is null), which involves creating a new circular list with the insertVal as its single element.

After inserting the new value into the proper position, it is crucial that the list maintains a complete circular and sorted order, challenging us to find the right insertion point. If there are multiple suitable positions due to duplicate values or placements between values with large differences, the choice of insertion point is flexible.

Examples

Example 1

Input:

head = [3,4,1], insertVal = 2

Output:

[3,4,1,2]

Explanation:

The list is circular: 3 → 4 → 1 → (back to 3).
The value 2 fits between 1 and 3, since it's greater than 1 and less than 3.

Example 2

Input:

head = [], insertVal = 5

Output:

[5]

Explanation:

List was initially empty. A single node with value 5 is created, pointing to itself.

Example 3

Input:

head = [1,1,1], insertVal = 2

Output:

[1,1,1,2]

Explanation:

All values are the same. The value 2 can be inserted anywhere.

Constraints

• The number of nodes in the list is in the range [0, 5 * 10^4].
• -10^6 <= Node.val, insertVal <= 10^6

Approach and Intuition

1. Handle an Empty List:

   • If the input node is null, create a new node with insertVal and set its next to itself. This forms a valid circular list of one element.
   • Return the new node.

2. Traverse to Find Insertion Point:

   • Initialize curr = head.

   • Continue traversing the list using curr = curr.next while checking:

     • Normal Case: If curr.val <= insertVal <= curr.next.val, insert the new node between curr and curr.next.

     • Rotation Point: If curr.val > curr.next.val, we've reached the largest-to-smallest transition:

       • Insert if insertVal >= curr.val (larger than max) or insertVal <= curr.next.val (smaller than min).

   • If no suitable spot is found after a full loop, insert the value at any point (e.g., after curr). This handles cases like all nodes having the same value.

3. Insert the New Node:

   • Allocate a new node with insertVal.
   • Point it to curr.next, and update curr.next to point to the new node.
   • Return the original head.

This strategy ensures the circular and sorted structure is maintained with minimal traversal and constant space usage.

Solutions

class Solution {
  public Node addNode(Node head, int value) {
    if (head == null) {
      Node createdNode = new Node(value, null);
      createdNode.next = createdNode;
      return createdNode;
    }

    Node previous = head;
    Node current = head.next;
    boolean shouldInsert = false;

    do {
      if (previous.val <= value && value <= current.val) {
        // Exact position found case
        shouldInsert = true;
      } else if (previous.val > current.val) {
        // Wrap around case
        if (value >= previous.val || value <= current.val)
          shouldInsert = true;
      }

      if (shouldInsert) {
        previous.next = new Node(value, current);
        return head;
      }

      previous = current;
      current = current.next;
    } while (previous != head);

    // Fallback if not inserted in loop
    previous.next = new Node(value, current);
    return head;
  }
}