You are given a circular linked list that is sorted in non-descending order.
The given list is represented as a List<Integer>. The first value in the list represents the node reference that is given to you. This node may be any node in the circular linked list and does not have to be the smallest value.
Insert insertVal into the circular linked list so that the list still remains sorted in circular non-descending order.
If more than one insertion position is valid, insert insertVal after the first valid position encountered while scanning from the first element of circularList.
If the list is empty, create a new circular linked list containing only insertVal.
Return the values of the circular linked list after insertion, starting from the same originally given node when the input list is non-empty. If the input list is empty, return a list containing only the inserted value.
Method Signature
List<Integer> insertIntoSortedCircularList(List<Integer> circularList, int insertVal)
circularList represents the circular linked list values starting from the given node reference.insertVal is the value that must be inserted into the circular linked list.- The method returns the circular linked list values after insertion.
- If
circularList is non-empty, the returned list must start with the same first value as the input list.
- If
circularList is empty, the returned list must contain exactly one value: insertVal.
Input Representation
The actual linked list nodes are represented using a List<Integer>.
For example, [3, 4, 1] means the circular linked list contains nodes in this circular order: 3 -> 4 -> 1 -> 3.
The first element of the list represents the given node reference.
Output Representation
Return a List<Integer> showing the circular linked list after insertion.
When the input list is non-empty, the returned list must start from the same originally given node reference.
If multiple insertion positions are valid, the returned list must reflect inserting insertVal after the first valid position encountered while scanning from the first element of circularList.
Rules
- The circular linked list is sorted in non-descending order.
- The given node may be any node in the circular list.
- The smallest value may appear somewhere in the middle of the given list representation.
- The largest value is followed by the smallest value because the list is circular.
- After insertion, the circular linked list must still be sorted in circular non-descending order.
- If multiple insertion positions are valid, insert
insertVal after the first valid position encountered while scanning from the first element of circularList.
- No parameter value will be
null.
- An empty circular linked list is represented by an empty list
[].
Deterministic Insertion Rule
When scanning the list, consider each adjacent pair
current and
next in circular order, including the pair from the last element back to the first element.
Insert
insertVal after the first
current where one of the following is true:
current <= insertVal <= next, meaning insertVal belongs between two non-decreasing values.current > next and insertVal >= current, meaning insertVal is greater than or equal to the largest value and belongs at the circular boundary.current > next and insertVal <= next, meaning insertVal is less than or equal to the smallest value and belongs at the circular boundary.
If no such pair is found, all existing values are equal, so insert
insertVal after the first element.
Constraints
0 ≤ circularList.size() ≤ 50,000-1,000,000 ≤ circularList[i] ≤ 1,000,000-1,000,000 ≤ insertVal ≤ 1,000,000circularList is sorted in circular non-descending order.
Examples
Example 1
Input: insertIntoSortedCircularList(circularList = [4, 1, 3], insertVal = 2)
Output: [4, 1, 2, 3]
Explanation: The list represents the circular order 4 -> 1 -> 3 -> 4. The sorted circular order is equivalent to 1 -> 3 -> 4 -> 1. While scanning from the first element, 2 is not valid between 4 and 1, but it is valid between 1 and 3. The returned list starts from the originally given node value 4.
Example 2
Input: insertIntoSortedCircularList(circularList = [], insertVal = 5)
Output: [5]
Explanation: The list is empty, so a new single-node circular linked list is created.
Example 3
Input: insertIntoSortedCircularList(circularList = [1], insertVal = 0)
Output: [1, 0]
Explanation: The circular order becomes 1 -> 0 -> 1. This is valid because the largest value 1 is followed by the smallest value 0. The returned list starts from the originally given node value 1.
Example 4
Input: insertIntoSortedCircularList(circularList = [3, 3, 3], insertVal = 3)
Output: [3, 3, 3, 3]
Explanation: While scanning from the first element, the first valid position is between the first 3 and the second 3. The value 3 is inserted after the first element.
Example 5
Input: insertIntoSortedCircularList(circularList = [3, 5, 1], insertVal = 6)
Output: [3, 5, 6, 1]
Explanation: The value 6 is greater than every existing value. While scanning from the first element, the first valid circular boundary is between 5 and 1, so 6 is inserted there. The returned list starts from the originally given node value 3.