Insert Linked Nodes into a Sorted Chain
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Sort a singly linked list using insertion sort and return its new head. Repeatedly take the next unprocessed node and insert it at a suitable position in the already sorted chain. Move nodes into that chain in place.
```cpp
ListNode* insertionSortList(ListNode* head);
```
`ListNode` has `val` and `next`. Example brackets display linked nodes, not an array input or return. No additional equal-key identity ordering is specified.
### Examples
```text
Input chain: [6,2,5,1]
Output chain: [1,2,5,6]
```
```text
Input chain: [0,-3,2,-3]
Output chain: [-3,-3,0,2]
```
### Constraints
- There are between 1 and 5000 nodes.
- Values lie between -5000 and 5000, inclusive.
- Use insertion sort, rather than substituting a different sorting algorithm.
Overview: Sort original linked-list nodes by repeated in-place insertion into a nondecreasing chain.
