Sort the chain
Sort a linked list with merge sort - split it at the middle, sort both halves, and merge them. About 20 minutes.
Split, sort, merge
Quicksort and heapsort need to jump to positions, which a chain does not allow. Merge sort needs only two things - splitting at the middle and merging two sorted lists - and a chain does both well.
Find the end of the first half with slow and fast pointers, cut the link after it, and sort each half by calling the same function. A list with zero or one nodes is already sorted.
if head is None or head.next is None:
return head # 0 or 1 node: sortedCut 7, 3, 9, 1, 5, 2 in the middle into 7, 3, 9 and 1, 5, 2.
Cut before you recurse
After finding the middle, the second half starts at the node after slow. Save it, then set slow.next to nothing, which ends the first half there.
Starting fast one node ahead of slow makes the first half the smaller one for even lengths. That matters: for two nodes it makes the halves one node each, so the recursion always gets shorter and always stops.
second = slow.next slow.next = None
Why is merge sort a good fit for a linked list?
- AIt only needs to split at the middle and to merge, and both are cheap on a chain
- BIt looks up items by position quickly
- CIt needs no recursion
Show the answer
It only needs to split at the middle and to merge, and both are cheap on a chain. Both moves work by relinking nodes with no random access and no extra array.
Sort a linked list
Given the head of a singly linked list, sort it in ascending order and return the head of the sorted list. Aim for n log n time.
head = [4, 2, 1, 3] → [1, 2, 3, 4]
0 ≤ number of nodes ≤ 5,000 · -100,000 ≤ node.val ≤ 100,000