Sort a Chain
MediumLinked List
Problem
A ranking service keeps scores in a singly linked list in arrival order. Before publishing, the list must be sorted.
Given the head, sort the list in non-decreasing order by relinking its nodes and return the new head, in O(n log n) time.
Example 1
- Input:
- head = [4, 2, 1, 3]
- Output:
- [1, 2, 3, 4]
Example 2
- Input:
- head = [-1, 5, 3, 4, 0]
- Output:
- [-1, 0, 3, 4, 5]
Negative values sort before zero.
Constraints
- 0 ≤ number of nodes ≤ 5 · 10^4
- -10^5 ≤ node.val ≤ 10^5
Hint
Show the first hint
Quick sort and heap sort rely on random access. Which O(n log n) sort only needs sequential access?
Walkthrough
How to approach it
01Clarify before coding
- Can there be duplicates and negatives? Yes.
- Relink or rewrite values? Relink nodes.
- Is O(n log n) required? Yes; O(n²) insertion sort is too slow at 5 · 10^4 nodes.
02Brute force
Insertion sort: take nodes one by one and insert each into its place in a growing sorted list.
Cost: O(n²) time in the worst case, about 1.25 · 10^9 steps at the limit.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.