Insert Node into Sorted Linked List
Given the head of a singly linked list whose node values are sorted in non-decreasing order, and an integer val, insert a new node with value val into the list such that the list remains sorted in non-decreasing order.
Return the node values of the modified linked list as an array.
If the initial linked list is empty (represented as []), return an array containing only val.
[ "[1, 3, 5, 7]", "4" ]
[ 1, 3, 4, 5, 7 ]
Explanation. Inserting 4 into the sorted list [1, 3, 5, 7] places it between 3 and 5, producing [1, 3, 4, 5, 7].
[ "[2, 4, 6]", "1" ]
[ 1, 2, 4, 6 ]
Explanation. Since 1 is smaller than the first element 2, it is inserted at the beginning of the list.
[ "[1, 2, 3]", "5" ]
[ 1, 2, 3, 5 ]
Explanation. Since 5 is greater than all existing elements, it is appended to the tail of the list.
[ "[]", "10" ]
[ 10 ]
Explanation. Inserting 10 into an empty list results in a list with a single node containing 10.
[ "[5]", "5" ]
[ 5, 5 ]
Explanation. Inserting a duplicate value 5 into [5] maintains the non-decreasing order resulting in [5, 5].
Follow-up: Can you perform the insertion in $O(1)$ extra space by modifying node pointers in-place?
- The number of nodes in the list is in the range `[0, 10^4]`. - `-10^5 <= Node.val <= 10^5` - `-10^5 <= val <= 10^5` - The input list is guaranteed to be sorted in non-decreasing order.
- Views
- 11