Insert Node into Sorted Linked List

easy

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.

Example 1

Input

[
  "[1, 3, 5, 7]",
  "4"
]

Output

[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].

Example 2

Input

[
  "[2, 4, 6]",
  "1"
]

Output

[1, 2, 4, 6]

Explanation. Since 1 is smaller than the first element 2, it is inserted at the beginning of the list.

Example 3

Input

[
  "[1, 2, 3]",
  "5"
]

Output

[1, 2, 3, 5]

Explanation. Since 5 is greater than all existing elements, it is appended to the tail of the list.

Example 4

Input

[
  "[]",
  "10"
]

Output

[10]

Explanation. Inserting 10 into an empty list results in a list with a single node containing 10.

Example 5

Input

[
  "[5]",
  "5"
]

Output

[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?

Constraints:

- 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: 1