You are given a singly linked list. Sort it with insertion sort and return the sorted list.
Insertion sort works like this:
- Keep a sorted list at the front. At first it holds only the first node.
- Take the next node from the input, find the right place for it inside the sorted list, and insert it there.
- Repeat until no input nodes are left.
How the judge passes the data
Examples
Example 1:
Input: head = [6,2,9,1]
Output: [1,2,6,9]
Explanation: After sorting, the values are 1, 2, 6, 9.
Example 2:
Input: head = [5,5,2]
Output: [2,5,5]
Explanation: The two 5s stay together, and the 2 moves to the front.
Example 3:
Input: head = [8]
Output: [8]
Explanation: A list with one node is already sorted.