Sort a Linked Chain with Constant-Workspace Merge Passes
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the head of a singly linked list after sorting it in ascending, nondecreasing value order. Keep the original `ListNode` pointer interface; `ListNode` contains `val` and `next`.
```cpp
ListNode* sortList(ListNode* head);
```
Brackets show values along a chain and are not array parameters. Equal values are allowed; no extra identity tie ordering is required.
### Examples
```text
Input chain: [7,-2,4,0]
Output chain: [-2,0,4,7]
```
```text
Input chain: []
Output chain: []
```
### Constraints
- There are between 0 and 50000 nodes.
- Values range from -100000 to 100000.
### Optional follow-up
Can you sort in `O(n log n)` time using only `O(1)` extra memory?
Overview: Sort a linked list by iterative doubling-width merges while meeting the constant-extra-space follow-up.