147. Insertion Sort List
You receive head, the first node of a singly linked list. Sort the list into ascending order the way insertion sort does: maintain a growing sorted chain at the front, repeatedly detach the next unsorted node, walk the sorted chain from its start until you find the first position where the node belongs, and splice it in there. Return the head node of the fully sorted list.
The list has at least one node; values can repeat and can be negative.
Example 1:
Input: head = [4, 2, 1, 3]
Output: [1, 2, 3, 4]
Explanation: Start with the sorted chain [4]. Insert 2 before 4 → [2, 4]. Insert 1 at the front → [1, 2, 4]. Insert 3 between 2 and 4 → [1, 2, 3, 4].
Example 2:
Input: head = [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]
Explanation: Each node is pulled off the unsorted remainder and spliced into its slot: negatives and zero land at the front, giving [-1, 0, 3, 4, 5].
Constraints:
- 1 ≤ number of nodes ≤ 5000
- -5000 ≤ node value ≤ 5000
Hints:
Put a dummy node in front of the sorted chain. Then inserting before the current smallest element is no longer a special case — every splice looks the same.
For each node, scan from the dummy while `scan.next.val < node.val`, then rewire: `node.next = scan.next; scan.next = node`. Detach the node from the unsorted part *before* splicing, and remember its old `next` so you can continue.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [4, 2, 1, 3]
Expected output: [1, 2, 3, 4]