The problem
Sort a linked list into increasing order and return the new head. Relink the nodes you are given; do not make new ones.
list 4, 2, 1, 3 -> 1, 2, 3, 4
list 3, 1, 3, 1, 2 -> 1, 1, 2, 3, 3
The tests build the list from nodes with a value and a next, pass you the head, then walk from the head you return, following next, and compare the values they find. An empty list is None.
sorted() and .sort() are switched off. Your sort must be O(n log n).
Limits
- Up to 100,000 nodes, with whole-number values between −1,000,000 and 1,000,000.
Builds on LINK-5 Fast and slow pointers and LINK-6 Merging lists.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Four values | Not run | |
| 2 | Empty | Not run | |
| 3 | One | Not run | |
| 4 | Two, wrong way round | Not run | |
| 5 | Repeats | Not run | |
| 6 | Already sorted | Not run | |
| 7 | Negative values | Not run | |
| 8 | Same nodes | Not run | |
| 9 | 100,000 values | Not run |