Merging & Sorting Lists

Merging two sorted lists is the linked-list skill that everything else in this note builds on. You only relink existing nodes, so a merge needs $O(1)$ extra space. Add a fast/slow split and you get merge sort, the natural $O(n \log n)$ sort for linked lists. Add a heap and you can merge k lists at once.

The idea#

Merge: keep a dummy node and a tail. While both lists have nodes, splice the smaller head onto tail and advance that list. When one list runs out, the other is already sorted. So attach the whole remainder in one step: tail.next = l1 or l2.

Sort: once you can merge, sorting is three steps. Merge sort fits linked lists even better than arrays.

Split the list in half with fast and slow pointers, and cut it (slow.next = None).
Sort each half recursively.
Merge the two sorted halves.

Why merge sort and not quicksort? A list has no random access, so quicksort and heapsort lose their advantages. Merging, on the other hand, needs no extra array on a list.

How to spot it#

These signals point to a merge or a merge sort.

"Merge two (or k) sorted lists."
"Sort a linked list", especially with an $O(n \log n)$ time or $O(1)$ extra space requirement.
A step that combines two already-ordered chains, after you split or reverse something.

Template#

This is the merge. It relinks nodes onto a dummy tail and creates nothing new.

dummy = new node; tail = dummy
while l1 is not None and l2 is not None:
    if l1.val <= l2.val:             # <= keeps equal items in order
        tail.next = l1; advance l1
    else:
        tail.next = l2; advance l2
    tail = tail.next
tail.next = whichever list is not empty   # attach the rest in one step
return dummy.next

Merge sort shape#

Merge sort wraps the merge in a split-and-recurse step. Use the first-middle split so two nodes split 1 + 1.

sort(head):
    if the list has 0 or 1 nodes: return head
    slow = head; fast = head.next    # first middle
    while fast is not None and fast.next is not None:
        slow moves 1 step; fast moves 2 steps
    mid = slow.next; slow.next = None    # cut the list in two
    return merge(sort(head), sort(mid))

Time is $O(n \log n)$ . Space is $O(\log n)$ for the recursion stack; the merges themselves allocate nothing but a dummy.

Pitfalls#

Watch for these. Each one causes infinite recursion or wasted work.

Splitting at the wrong middle. With fast = head, a two-node list splits into 2 + 0 and the recursion never ends. Start fast = head.next.
Forgetting to cut. Without slow.next = None, the left half still runs into the right half.
Copying the tail node by node. Once one list is empty, tail.next = l1 or l2 attaches the rest in $O(1)$ .
Creating new nodes. Relink the existing ones. The problem usually expects it, and it keeps space at $O(1)$ .
Merging many lists one by one. That costs $O(nk)$ for k lists. A heap does better.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Merge Two Sorted Lists

This is the merge template. Start from a dummy, splice the smaller head each time, and attach the leftover list with one link.

Hint: Sort List

Split with fast and slow pointers, with fast starting at head.next. Cut the list, sort each half recursively, then merge.

Hint: Reorder List

Combine three pieces. Find the middle, reverse the second half, then merge the two halves. The merge alternates nodes instead of comparing values.

Hint: Merge k Sorted Lists

Put the head of each list in a min-heap keyed by value. Pop the smallest, append it, and push its next. Store (val, index, node) tuples so ties never compare two ListNode objects. This is $O(n \log k)$ ; see K-Way Merge.

Key takeaways#

Merge with a dummy and a tail; attach the leftover list with tail.next = l1 or l2.
Merge sort is the list sort: split with fast/slow, cut, sort halves, merge.
Use the first-middle split (fast = head.next) so two nodes split 1 + 1.
Merging k lists is a heap problem: $O(n \log k)$ .

Core idea#

Merge two sorted lists by splicing the smaller head onto a dummy tail. Add a fast/slow split and you get merge sort, the natural $O(n \log n)$ sort for linked lists.

Key points#

Merge relinks existing nodes, so it needs $O(1)$ extra space.
When one list runs out, attach the rest in one step: tail.next = l1 or l2.
Use <= in the merge to keep equal items in order.
Sort: split with fast/slow, cut with slow.next = None, sort each half, merge.
Lists have no random access, so quicksort and heapsort lose their advantages.
Merge sort on a list takes $O(n \log n)$ time and $O(\log n)$ stack space.
Merge k lists with a min-heap of (val, index, node): $O(n \log k)$ . One-by-one merging costs $O(nk)$ .
Reorder List: find the middle, reverse the second half, merge by alternating nodes.

Template#

merge(l1, l2):
    dummy = tail = new node
    while l1 and l2 both have nodes:
        splice the smaller head (<= keeps order) onto tail
        advance that list; tail = tail.next
    tail.next = whichever list is left   # one link
    return dummy.next

sort(head):
    if 0 or 1 nodes: return head
    slow = head; fast = head.next    # first middle: 2 split 1 + 1
    while fast and fast.next: slow 1 step, fast 2 steps
    mid = slow.next; slow.next = None    # cut
    return merge(sort(head), sort(mid))

Pitfalls#

fast = head for the split. A two-node list splits 2 + 0 and the recursion never ends.
No cut. The left half still runs into the right half.
Copying the leftover node by node instead of one link.
Creating new nodes instead of relinking.

Say it in an interview#

"Merge sort is the list sort: split with fast and slow, cut, sort halves, merge."
"For k lists, a min-heap of heads gives O(n log k)."