Insertion Sort List
You are 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:
- Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
- At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
- It repeats until no input elements remain.
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:
1 <= The length of the list <= 5000.-5000 <= Node.val <= 5000