Practice/Meta/Leetcode 708. Insert into a Sorted Circular Linked List

Leetcode 708. Insert into a Sorted Circular Linked List

CodingMust

Problem

You are given a reference to a node in a sorted circular linked list. The list is sorted in ascending order, and the last node points back to the first node, forming a circle.

Your task is to insert a new value into this circular list while maintaining the sorted order. After insertion, return a reference to any node in the modified list.

The circular linked list may be empty (given as None), in which case you should create a new single-node circular list.

Requirements

1. Insert the new value into its correct position to maintain sorted order
2. Handle the case where the list is empty
3. Handle insertion at the "wrap-around" point (between the maximum and minimum values)
4. Maintain the circular structure of the list
5. Return a reference to any node in the resulting list

Constraints

• The number of nodes in the list is in the range [0, 5000]
• -106 ≤ Node values ≤ 106
• -106 ≤ insertVal ≤ 106
• All values in the original list are sorted in non-decreasing order

Examples

Example 1:

Input: head = [1, 3, 5], insertVal = 4 Output: [1, 3, 4, 5] Explanation: The value 4 fits between 3 and 5 in sorted order.

Example 2:

Input: head = [1, 3, 5], insertVal = 0 Output: [0, 1, 3, 5] Explanation: 0 is the new minimum and should be inserted at the wrap-around point (after 5, before 1).

Example 3:

Input: head = [], insertVal = 1 Output: [1] Explanation: The list is empty, so we create a new node that points to itself.

Example 4:

Input: head = [3, 3, 3], insertVal = 3 Output: [3, 3, 3, 3] Explanation: When all values are equal, we can insert anywhere.