708. Insert into a Sorted Circular Linked List - Detailed Explanation

Problem Statement:

You are given a node from a circular linked list that is sorted in non-decreasing order. (A circular linked list means the last node’s next pointer points to some node in the list, not necessarily the head.) Write a function to insert a new value insertVal into the list such that it remains a sorted circular list. The given node can be any single node in the list. If the list is empty (i.e. the given node is null), create a new single circular list and return that node.

Example Inputs and Outputs:

1. Example 1:

   • Input:
     • List: [3 -> 4 -> 1] (Note: The list is circular; here, 1 points back to 3.)
     • insertVal = 2
   • Output: A circular linked list such as [3 -> 4 -> 1 -> 2] (or the equivalent rotation)
   • Explanation: The new value 2 is inserted between 1 and 3 (or at the appropriate spot in the sorted order).

2. Example 2:

   • Input:
     • List: [] (empty list)
     • insertVal = 1
   • Output: A single-node circular list [1]
   • Explanation: Since the list is empty, create a new node that points to itself.

3. Example 3:

   • Input:
     • List: [1 -> 1 -> 1]
     • insertVal = 0
   • Output: A circular linked list containing [1, 1, 1, 0]
   • Explanation: All nodes have the same value, so the new value can be inserted anywhere.

Constraints:

• The list is sorted in non-decreasing order.
• The list is circular (i.e. the last node’s next pointer points back to some node in the list).
• The given node can be any node in the list.
• If the list is empty, you must create a new single-node circular list.

Hints for Solving the Problem:

1. Handling an Empty List:

   • If the input node is null, create a new node, set its next pointer to itself, and return that node.

2. Traversal in a Circular List:

   • Since the list is circular, use a do-while loop (or its equivalent) to traverse the list until you return to the starting node.

3. Finding the Insertion Point:

   • Look for the correct position between two nodes (let’s call them curr and curr.next) where the new value should be inserted.
   • Case A: If curr.val <= insertVal <= curr.next.val, then insert between them.
   • Case B: If you find a “turning point” (where curr.val > curr.next.val), then the list is wrapping from the largest element back to the smallest. In this case, if insertVal is either greater than or equal to curr.val (new maximum) or less than or equal to curr.next.val (new minimum), then insert there.
   • Case C: If no proper spot is found after one complete loop (this happens when all nodes have the same value), insert the new node anywhere.

Approach: One-Pass Insertion by Traversing the Circular List

Step-by-Step Explanation:

1. Empty List Check:

   • If the provided node is null, create a new node with insertVal, point its next to itself, and return it.

2. Initialize Traversal:

   • Start from the given node and use a pointer (curr) to traverse the list.

3. Search for the Insertion Point:

   • Use a loop (do-while style) to examine each pair of consecutive nodes (curr and curr.next).

   • Normal Case: If curr.val <= insertVal <= curr.next.val, then the proper spot is found.

   • Edge Case (Wrapping Point): If you encounter a node where curr.val > curr.next.val, then the list is wrapping around. In this case, if insertVal is greater than or equal to curr.val (i.e., it should be the new maximum) or less than or equal to curr.next.val (i.e., it should be the new minimum), then insert between curr and curr.next.

   • Fallback: If you complete one full loop without finding a valid insertion point (e.g., when all nodes have the same value), simply insert the new node anywhere (typically after the starting node).

4. Insertion:

   • Create a new node, set its next pointer to curr.next, and update curr.next to point to the new node.

5. Return the (possibly unchanged) head of the list.

Python Code: