Insert into cyclic list and Tree diameter
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.
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.