Insert Value into a Circular Sorted Linked List

Problem Statement

Given a reference to any node of a circular linked list sorted in ascending order, write a function to add a new integer value so that the list remains sorted and circular. The given node can be any node in the list and may not be the node with the smallest value.

If multiple valid positions exist for the insertion, you may insert the new value at any one of them. After inserting, the list must still maintain its circular sorting order.

If the list is empty (i.e., the given node is null), create a new circular list containing only the new value and return a reference to this node. Otherwise, return the original given node.

Examples

Input:
List: 4 → 6 → 1 → (back to 4)
Given node: node with value 6
Insert value: 5

Output:
List after insertion: 4 → 5 → 6 → 1 → (back to 4)
Return the node with value 6.

---

Input:
List: empty (null)
Insert value: 10

Output:
New list with one node: 10 → (points to itself)
Return the node with value 10.

---

Input:
List: 2 → 3 → 5 → (back to 2)
Given node: node with value 3
Insert value: 0

Output:
List after insertion: 0 → 2 → 3 → 5 → (back to 0)
Return the node with value 3.
    

Constraints

• The number of nodes in the list is between 0 and 500.
• Each node's value is an integer between -500 and 500.
• The value to be inserted is an integer between -1000 and 1000.