147. Insertion Sort List
Medium
30 Points
Linked List
Sorting
Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.
The steps of the insertion sort algorithm:
The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.
Examples
Example 1
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Constraints
The number of nodes in the list is in the range [1, 5000].-5000 <= Node.val <= 5000
147. Insertion Sort List
Medium
30 Points
Linked List
Sorting
Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.
The steps of the insertion sort algorithm:
The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.
Examples
Example 1
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Constraints
The number of nodes in the list is in the range [1, 5000].-5000 <= Node.val <= 5000