Appendix C. Merging k sorted lists, the long version

Warning. This is the first version of chapter 10, kept whole. It walks through eleven programs for one merge, and most of them are near copies of each other. It is very ugly. It stays in the book for brave readers who want every variant and every borrow trick. Chapter 10 teaches the same material with three programs.

Chapter 9 built singly linked lists and moved their nodes between owners with take. Here you have k linked lists, each already sorted, and you want one sorted list that contains all their nodes.

Section C.2 compares three orders of merging. Sections C.3 to C.8 implement them in eleven programs, and section C.9 lists the time and memory each program needs.

Two letters appear throughout. k is the number of lists. N is the total number of nodes across all of them.

C.1 Merging two sorted lists

Every program in this chapter merges two sorted lists at a time. Compare the front nodes of the two lists. Move the smaller one to the end of the output. Repeat until one list is empty, then attach the other list whole. Figure C.1 works through an example.

With linked lists, “move a node to the output” does not copy the value. It detaches the node from the front of its list and links it to the end of the output. No memory is allocated.

Animation C.1 runs that merge with the code of listing C.5, one node at a time. The output starts at a dummy node, a placeholder whose next will hold the real first node. tail always points at the last node of the output.

C.2 Three strategies for k lists

Figure C.2 shows three ways to extend two-list merging to k lists.

One at a time. Merge list 2 into list 1, then list 3 into the result, and so on. Each merge walks the whole result so far, which keeps growing. The first nodes are walked k times, so the total is about O(kN).

Pairwise rounds. Merge the lists in pairs, like the rounds of a tournament. After the first round there are k / 2 lists, after the second k / 4, and so on. In every round, each node takes part in exactly one merge. There are about log₂ k rounds, so the total is O(N log k).

A heap of heads. Put the front node of each list into a min-heap, the structure from chapter 5. Pop the smallest, append it to the output, and push the next node from the same list. Each node goes through one push and one pop on a heap of at most k entries. Each costs O(log k), so the total is again O(N log k).

Animation C.2 counts node moves for eight lists of three nodes: pairwise rounds against one list at a time.

For 100 lists of 10,000 nodes each, N is a million. O(kN) is about 100 million steps. O(N log k) is about 7 million.

The pairwise strategy has a compact in-place form that most of the eleven versions use. It keeps the lists in a Vec and merges positions that are a growing interval apart (figure C.3).

In each round, the list at position i absorbs the list at i + interval. The position i runs through 0, 2 × interval, 4 × interval, and so on. The odd list out, number 4 here, waits until the interval is large enough to reach it.

C.3 First version: split_at_mut and a dummy head

The first version implements pairwise rounds with a growing interval, as in figure C.3. Its merge builds the output after a placeholder node, called a dummy head, so that the first real node needs no special case.

Listing C.1 The node type and the interval loop (lines 1 to 34). src/bin/merge_k_sorted_lists_divide.rs

struct MergeKSorted {}

#[derive(Default)]
struct ListNode {
    data: u32,
    next: Option<Box<ListNode>>,
}
impl ListNode {
    fn new(data: u32) -> Self {
        Self { data, next: None }
    }
}

type OptionalLink<T> = Option<Box<T>>;

impl MergeKSorted {
    pub fn merge_k_lists(mut lists: Vec<OptionalLink<ListNode>>) -> OptionalLink<ListNode> {
        if lists.is_empty() {
            return None;
        }

        let (n, mut interval) = (lists.len(), 1);
        while interval < n {
            let mut i = 0;
            while i + interval < n {
                let (left, right) = lists.split_at_mut(i + interval);
                left[i] = Self::merge_two(&mut left[i], &mut right[0]);
                i += interval * 2;
            }
            interval *= 2;
        }

        lists[0].take()
    }
    // ...
}

ListNode is the node from chapter 9: a value, data, and next, an Option<Box<ListNode>> that is None at the end of the list. OptionalLink<T> is a type alias, a second name for Option<Box<T>>, so signatures stay short. MergeKSorted is an empty struct. It holds no data, and only groups the functions under one name.

The two while loops follow figure C.3. The outer one doubles interval. The inner one steps i by interval * 2, merging i with i + interval.

The merge needs to change two elements of the vector at once. The obvious code, merge_two(&mut lists[i], &mut lists[i + interval]), does not compile. Both &mut borrows are borrows of the whole vector lists, and Rust allows only one mutable borrow of a value at a time. The compiler does not reason about the two indexes being different.

split_at_mut(i + interval) solves this. It splits the vector into two slices that do not overlap: the part before position i + interval and the rest. It returns a mutable borrow of each. Now left[i] and right[0] come from different slices, and borrowing both is allowed.

The merge of two lists uses a dummy head and a tail pointer (figure C.4).

Listing C.2 Merging two lists (lines 36 to 57).

impl MergeKSorted {
    // ...
    fn merge_two(
        left: &mut OptionalLink<ListNode>,
        right: &mut OptionalLink<ListNode>,
    ) -> OptionalLink<ListNode> {
        let mut dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;

        while let (Some(l), Some(r)) = (left.as_ref(), right.as_ref()) {
            let smaller = if l.data < r.data {
                &mut *left
            } else {
                &mut *right
            };
            let mut head = smaller.take().unwrap();
            *smaller = head.next.take();
            tail.next = Some(head);
            tail = tail.next.as_mut().unwrap();
        }

        tail.next = left.take().or(right.take());
        dummy.next
    }
}

dummy is a throwaway node, and tail is a mutable reference to the last node of the output. At the start, the output is empty, so tail points at dummy. Each pass of the loop:

1. while let (Some(l), Some(r)) = (left.as_ref(), right.as_ref()) continues while both lists have a front node, and looks at both without moving them.
2. smaller is a mutable reference to whichever list has the smaller front.
3. smaller.take().unwrap() takes that front node out, and *smaller = head.next.take() puts the rest of that list back.
4. tail.next = Some(head) attaches the node, and tail = tail.next.as_mut().unwrap() moves tail onto it.

When one list runs out, left.take().or(right.take()) attaches whichever one is left. The merged list starts at dummy.next.

The complete program is listing C.19 at the end of the chapter.

The tests check three lists, an empty input with empty lists inside it, and an odd number of lists.

$ cargo run --bin merge_k_sorted_lists_divide
[1, 1, 2, 3, 4, 4, 5, 6]

C.4 Avoiding the double borrow

split_at_mut works, but the next two versions show that the double borrow can be avoided altogether.

C.4.1 Take the right list out first

This version moves the right-hand list out of the vector before the call. With only one list still inside the vector, the merge needs only one mutable borrow of it.

It uses the same MergeKSorted, ListNode, and OptionalLink as listing C.1.

Listing C.3 The loop and the merge (lines 16 to 56). src/bin/merge_k_sorted_lists_swap.rs

impl MergeKSorted {
    pub fn merge_k_lists(mut lists: Vec<OptionalLink<ListNode>>) -> OptionalLink<ListNode> {
        if lists.is_empty() {
            return None;
        }

        let (n, mut interval) = (lists.len(), 1);
        while interval < n {
            let mut i = 0;
            while i + interval < n {
                let mut right = lists[i + interval].take();
                lists[i] = Self::merge_two(&mut lists[i], &mut right);
                i += interval * 2;
            }
            interval *= 2;
        }

        lists[0].take()
    }

    fn merge_two(
        left: &mut OptionalLink<ListNode>,
        right: &mut OptionalLink<ListNode>,
    ) -> OptionalLink<ListNode> {
        let mut dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;

        while let (Some(l), Some(r)) = (&left, &right) {
            if r.data < l.data {
                std::mem::swap(left, right);
            }
            let mut smallest = left.take().unwrap();
            *left = smallest.next.take();
            tail.next = Some(smallest);
            tail = tail.next.as_mut().unwrap();
        }

        tail.next = left.take().or(right.take());
        dummy.next
    }
}

Look at the inner loop:

let mut right = lists[i + interval].take();
lists[i] = Self::merge_two(&mut lists[i], &mut right);

The right list is moved out of the vector into a local variable first. After that, the only borrow of the vector is the one for lists[i], so the call compiles.

The merge changes too. Instead of choosing which list to take from, it makes sure left always holds the smaller front. When the right front is smaller, std::mem::swap(left, right) exchanges the two lists. Then the loop body always takes from left.

The complete program is listing C.20 at the end of the chapter.

C.4.2 Merge owned lists, with no dummy node

This version moves both lists out of the vector and passes them by value, so nothing is borrowed during the merge. It also drops the dummy node and tracks the empty slot where the next node belongs.

Listing C.4 The node type, the loop, and the merge (lines 1 to 43). src/bin/merge_k_sorted_lists_simple.rs

struct ListNode {
    data: u32,
    next: Link,
}

type Link = Option<Box<ListNode>>;

fn merge_k_lists(mut lists: Vec<Link>) -> Link {
    if lists.is_empty() {
        return None;
    }

    let (n, mut interval) = (lists.len(), 1);
    while interval < n {
        let mut i = 0;
        while i + interval < n {
            let left = lists[i].take();
            let right = lists[i + interval].take();
            lists[i] = merge_two(left, right);
            i += interval * 2;
        }
        interval *= 2;
    }

    lists[0].take()
}

fn merge_two(mut left: Link, mut right: Link) -> Link {
    let mut merged = None;
    let mut tail = &mut merged;

    while let (Some(l), Some(r)) = (&left, &right) {
        if r.data < l.data {
            std::mem::swap(&mut left, &mut right);
        }
        *tail = left; // hang left list on the tail
        tail = &mut tail.as_mut().unwrap().next; // step past its first node
        left = tail.take(); // cut the rest off again
    }

    *tail = left.or(right);
    merged
}

This file names its link type Link, an alias for Option<Box<ListNode>>, and uses free functions instead of methods on an empty struct. The algorithm changes in two ways.

First, merge_two takes both lists by value, not by reference. The loop moves both out of the vector with take() before the call, so nothing is borrowed at all.

Second, there is no dummy node. tail is a &mut Link, a pointer to the empty slot where the next node belongs. It starts at &mut merged, the slot for the first node. The loop body is three lines, each with a comment:

*tail = left;                              // hang left list on the tail
tail = &mut tail.as_mut().unwrap().next;   // step past its first node
left = tail.take();                        // cut the rest off again

After the swap has put the smaller front in left, the whole left list is placed in the empty slot. tail then moves to the next slot of the list’s first node. Finally tail.take() cuts everything after that first node back off into left. One node has moved to the output.

The complete program is listing C.21 at the end of the chapter.

to_vec takes &Link and follows the nodes with list = &node.next, so the tests can read a list without consuming it.

C.4.3 The shortest form, with Option::insert

This version keeps the owned merge and brings back the dummy head. One standard-library method attaches a node and moves the tail onto it in a single step.

Listing C.5 The node type, the merge, and the loop (lines 1 to 45). src/bin/merge_k_sorted_list_zero_copy.rs

type NodeLink = Option<Box<Node>>;

struct Node {
    val: i32,
    next: NodeLink,
}

fn merge_two(mut left: NodeLink, mut right: NodeLink) -> NodeLink {
    let mut dummy = Box::new(Node { val: 0, next: None });
    let mut tail = &mut dummy;

    while let (Some(left_head), Some(right_head)) = (&left, &right) {
        let smaller = if left_head.val <= right_head.val {
            &mut left
        } else {
            &mut right
        };
        let mut node = smaller.take().unwrap(); // safe: checked by while let
        *smaller = node.next.take();
        tail = tail.next.insert(node);
    }

    tail.next = if left.is_some() { left } else { right };
    dummy.next
}

fn merge_k(mut lists: Vec<NodeLink>) -> NodeLink {
    if lists.is_empty() {
        return None;
    }

    let list_count = lists.len();
    let mut gap = 1;
    while gap < list_count {
        let mut index = 0;
        while index + gap < list_count {
            let left = lists[index].take();
            let right = lists[index + gap].take();
            lists[index] = merge_two(left, right);
            index += gap * 2;
        }
        gap *= 2;
    }
    lists[0].take()
}

Here the node is Node, with an i32 value named val, and the link alias is NodeLink. This version keeps the owned merge_two from listing C.4 and brings back the dummy head. It shortens the tail bookkeeping with one method:

tail = tail.next.insert(node);

Option::insert stores a value in the option and returns a mutable reference to the stored value. So one call attaches the node and moves tail onto it. Listing C.2 needed two lines and an unwrap for the same step.

Every node in the output is a box that was in the input, moved by pointer. The only allocation is the dummy node, once per merge_two call. The single unwrap has a comment saying why it cannot fail. The while let has already checked that both lists have a front node.

The complete program is listing C.22 at the end of the chapter.

main tries four cases: four lists including an empty one, duplicates across lists, no lists at all, and five lists.

$ cargo run --bin merge_k_sorted_list_zero_copy
0 1 2 3 4 5 6 7 8 9
1 1 1 3 5

1 2 3 4 5 8 9

The empty line is the output for no lists.

C.4.4 Swap the lists by value

Listing C.5 picks the smaller list with &mut left or &mut right, and keeps a third mutable reference, tail. This version swaps the two lists by value instead, so that left always holds the smaller front node. The only mutable reference left is tail, which makes the loop easier to read: there is one borrow to follow instead of three.

Listing C.8 The node type and merge_two (lines 4 to 27). src/bin/merge_k_sorted_lists_owned.rs

type Link = Option<Box<Node>>;

struct Node {
    val: i32,
    next: Link,
}

/// Merge two sorted lists. O(n) time, O(1) extra memory.
fn merge_two(mut left: Link, mut right: Link) -> Link {
    let mut dummy = Box::new(Node { val: 0, next: None });
    let mut tail = &mut dummy;

    while let (Some(l), Some(r)) = (&left, &right) {
        if r.val < l.val {
            (left, right) = (right, left); // left now holds the smaller front
        }
        let mut node = left.unwrap(); // safe: checked by while let
        left = node.next.take();
        tail = tail.next.insert(node);
    }

    tail.next = left.or(right);
    dummy.next
}

while let (Some(l), Some(r)) = (&left, &right) runs while both lists have a node. &left and &right are shared references, used only to read the two front values.

If the right front is smaller, (left, right) = (right, left) swaps the two lists. The assignment moves the two Option values; no node moves, and no reference is taken. After it, the smaller front node is always in left.

left.unwrap() moves that list out of left. It cannot fail, because the while let checked that left is Some. node.next.take() cuts the front node off, and the rest of the list goes back into left.

tail.next.insert(node) attaches the node at the end of the output, as in listing C.5, and returns a reference to it. That node is the new tail.

When the loop ends, one list is empty. left.or(right) returns the other one, and tail.next takes it whole.

Animation C.3 runs merge_two one line at a time on the lists of the trace below. The table beside the lists shows what each variable owns or borrows after every line. The last part reads l after the swap, which does not compile.

Trace the merge of 1 → 4 with 2 → 3 → 5:

Each pass moves one node, so merging n nodes takes O(n) time. The merge uses O(1) extra memory, and allocates only the dummy node.

Listing C.8 merge_k (lines 29 to 47). src/bin/merge_k_sorted_lists_owned.rs

/// Merge k sorted lists in place: round 1 merges lists 1 apart, round 2 lists
/// 2 apart, and so on. O(N log k) time, O(1) extra memory.
fn merge_k(mut lists: Vec<Link>) -> Link {
    if lists.is_empty() {
        return None;
    }

    let size = lists.len();
    let mut gap = 1;
    while gap < size {
        let mut i = 0;
        while i + gap < size {
            lists[i] = merge_two(lists[i].take(), lists[i + gap].take());
            i += gap * 2;
        }
        gap *= 2;
    }
    lists[0].take()
}

merge_k is the loop of listing C.1. lists[i].take() moves each list out of its slot and leaves None, so merge_two receives two owned lists.

Animation C.4 runs the merge of the trace. The last part leaves out the line after the loop.

$ cargo run --bin merge_k_sorted_lists_owned
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 3, 5]
[]

The complete program is listing C.23 at the end of the chapter.

C.5 The same merge on an enum node

Chapter 9 also wrote a list as an enum. Two versions try the merge on that shape.

C.5.1 An enum with its own take

The node can also be an enum, as in chapter 9. A list is either Empty, or a Node with a value and the rest of the list. This version gives that enum a take method so the merge reads like the Option versions.

Listing C.9 The node type (lines 1 to 14). src/bin/merge_k_sorted_lists_enum.rs

use ListNode::{Empty, Node};

type LinkTo<T> = Box<T>;

enum ListNode {
    Node { data: u32, next: LinkTo<ListNode> },
    Empty,
}

impl ListNode {
    fn take(&mut self) -> ListNode {
        std::mem::replace(self, Empty)
    }
}

use ListNode::{Empty, Node}; lets the code write Empty instead of ListNode::Empty. The enum gets its own take, built on mem::replace, so it can be used like Option::take.

Listing C.10 The merge (lines 38 to 76).

impl MergeKSorted {
    // ...
    fn merge_two(left: &mut ListNode, right: &mut ListNode) -> ListNode {
        let mut left = left.take();
        let mut right = right.take();
        let mut merged = Empty;
        let mut tail = &mut merged;

        loop {
            let smaller = match (&left, &right) {
                (Empty, _) => {
                    *tail = right;
                    break;
                }
                (_, Empty) => {
                    *tail = left;
                    break;
                }
                (Node { data: l, .. }, Node { data: r, .. }) => {
                    if l <= r {
                        &mut left
                    } else {
                        &mut right
                    }
                }
            };

            if let Node { data, next } = smaller.take() {
                *smaller = *next;
                *tail = Node {
                    data,
                    next: LinkTo::new(Empty),
                };
                if let Node { next, .. } = tail {
                    tail = next;
                }
            }
        }

        merged
    }
}

The loop picks smaller with a match on both fronts. The two Empty arms attach the other list and leave the loop with break. The third arm returns a mutable reference to the list with the smaller front.

This representation has a cost. Look at how a node is attached:

*tail = Node { data, next: LinkTo::new(Empty) };

With Option<Box<Node>>, a node’s box moves from the input to the output. Here, *smaller = *next moves the rest of the input out of its box, and that box is freed. The output node is a new Node with a new Box holding a new Empty. So this version allocates once for every node it outputs.

The complete program is listing C.24 at the end of the chapter.

C.5.2 An enum with standard traits and a recursive merge

This version uses the same enum shape but derives Default, so the standard std::mem::take works on it. Its two-list merge is recursive.

Listing C.11 The type and its conversions (lines 1 to 24). src/bin/merge_k_sorted_lists_enum_recursive.rs

pub type NodeLink = Box<ListNode>;

#[derive(Debug, PartialEq, Eq, Default)]
pub enum ListNode {
    #[default]
    Empty,
    Node(i32, NodeLink),
}

impl From<Vec<i32>> for NodeLink {
    fn from(vec: Vec<i32>) -> Self {
        vec.into_iter()
            .rev()
            .fold(NodeLink::default(), |acc, v| {
                NodeLink::new(ListNode::Node(v, acc))
            })
    }
}

impl From<Vec<i32>> for ListNode {
    fn from(vec: Vec<i32>) -> Self {
        *NodeLink::from(vec)
    }
}

This version uses standard traits in place of hand-written helpers:

• #[derive(Default)] with #[default] on Empty makes the empty list the default value. So NodeLink::default() is a box holding Empty, and std::mem::take can be used instead of a custom take.
• impl From<Vec<i32>> for NodeLink builds a list from a vector. It walks the vector backward with rev() and uses fold to wrap each value around the list built so far. main calls it as vec![1, 4, 5].into().

Listing C.12 The interval loop and a recursive merge (lines 26 to 59).

impl ListNode {
    pub fn merge_k_lists(mut lists: Vec<NodeLink>) -> NodeLink {
        if lists.is_empty() {
            return NodeLink::default();
        }
        let mut interval = 1;
        while interval < lists.len() {
            for i in (0..lists.len()).step_by(interval * 2) {
                if i + interval < lists.len() {
                    let right = std::mem::take(&mut lists[i + interval]);
                    let left = std::mem::take(&mut lists[i]);
                    lists[i] = NodeLink::new(Self::merge(*left, *right));
                }
            }
            interval *= 2;
        }
        lists.swap_remove(0)
    }

    fn merge(l1: ListNode, l2: ListNode) -> ListNode {
        match (l1, l2) {
            (ListNode::Empty, l) | (l, ListNode::Empty) => l,
            (ListNode::Node(v1, n1), ListNode::Node(v2, n2)) => {
                if v1 <= v2 {
                    let rest = Self::merge(*n1, ListNode::Node(v2, n2));
                    ListNode::Node(v1, NodeLink::new(rest))
                } else {
                    let rest = Self::merge(ListNode::Node(v1, n1), *n2);
                    ListNode::Node(v2, NodeLink::new(rest))
                }
            }
        }
    }
}

std::mem::take(&mut lists[i + interval]) moves the right list out and leaves the default, an empty list, in its place. It takes the right list before the left, which avoids the double borrow as listing C.3 did. lists.swap_remove(0) removes position 0 by moving the last element into it, which takes O(1).

merge is recursive, and takes both lists as ListNode values. The caller moves them out of their boxes with *left and *right. merge keeps the smaller front node, merges the rest into rest, and boxes only the result. The list it did not take from passes to the recursive call unboxed. The code reads almost like a definition of merging. It has two costs. It allocates a new Box for every output node. And it recurses once per output node, so a long result uses a deep stack, as chapter 9’s recursive drop did.

The complete program is listing C.25 at the end of the chapter.

The program prints the result with {:#?}, which shows the nesting of the enum directly:

$ cargo run --bin merge_k_sorted_lists_enum_recursive
Node(
    1,
    Node(
        1,
        Node(
            2,
            ...

C.6 A queue of lists

This version does pairwise rounds with a queue instead of intervals. A VecDeque is a double-ended queue: you can push and pop at both ends in O(1). merge_k_lists puts all the lists in the queue. Then it pops two from the front and pushes their merge on the back, until one list is left.

This file declares its own copy of the node type, with Link as the alias for a whole list:

use std::collections::VecDeque;

struct ListNode {
    data: u32,
    next: Option<Box<ListNode>>,
}

type Link = Option<Box<ListNode>>;

Listing C.13 merge_k_lists (lines 10 to 18). src/bin/merge_k_sorted_lists_pairs.rs

fn merge_k_lists(lists: Vec<Link>) -> Link {
    let mut queue: VecDeque<Link> = lists.into();
    while queue.len() > 1 {
        let a = queue.pop_front().unwrap();
        let b = queue.pop_front().unwrap();
        queue.push_back(merge_two(a, b));
    }
    queue.pop_front().flatten()
}

Because merged lists go to the back, every original list is merged once before any merged list is merged again. So the rounds are the same as in figure C.2, and the cost is O(N log k).

queue.pop_front().flatten() needs a word of explanation. pop_front returns Option<Link>, and a Link is itself an Option<Box<ListNode>>. So the value is an Option<Option<...>>. flatten turns it into one Option: None if the queue was empty, or the merged list.

$ cargo run --bin merge_k_sorted_lists_pairs
1 1 2 3 4 4 5 6

C.7 A heap of list heads

This is the third strategy from figure C.2. The heap does not hold nodes. It holds pairs of (front value, list number), wrapped in Reverse to make it a min-heap, as in chapter 5. Storing the list number instead of the node keeps the nodes in their lists, and avoids needing an ordering on nodes.

Listing C.14 merge_k_lists (lines 10 to 33). src/bin/merge_k_sorted_lists_heap.rs

fn merge_k_lists(mut lists: Vec<Link>) -> Link {
    let mut heap = BinaryHeap::new();
    for (i, list) in lists.iter().enumerate() {
        if let Some(node) = list {
            heap.push(Reverse((node.data, i)));
        }
    }

    let mut dummy = Box::new(ListNode {
        data: 0,
        next: None,
    });
    let mut tail = &mut dummy;

    while let Some(Reverse((_, i))) = heap.pop() {
        let mut node = lists[i].take().unwrap();
        lists[i] = node.next.take();
        if let Some(next) = &lists[i] {
            heap.push(Reverse((next.data, i)));
        }
        tail = tail.next.insert(node);
    }
    dummy.next
}

Each pass of the loop:

1. Pops the smallest pair. Its second field, i, says which list holds that value.
2. Takes the front node out of lists[i] and puts the rest of that list back.
3. If the list still has a node, pushes that node’s value with i.
4. Attaches the taken node to the output with tail.next.insert(node).

When two fronts have equal values, the pairs compare by list number, so the lower-numbered list goes first.

The heap needs only the current front of each list. That makes this strategy the right one when the lists are too large to hold in memory. An example is k sorted files read line by line.

C.8 Recursion on halves

The last two versions do pairwise merging from the top down. They split the lists into two halves, merge each half recursively, and merge the two results.

Listing C.15 The node type and a recursive two-list merge (lines 1 to 21). src/bin/merge_k_sorted_lists_recursion.rs

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

type List = Option<Box<ListNode>>;

// Merge two sorted lists
fn merge(a: List, b: List) -> List {
    match (a, b) {
        (None, rest) | (rest, None) => rest,
        (Some(mut a), Some(mut b)) => {
            if a.val > b.val {
                std::mem::swap(&mut a, &mut b); // a is now the smaller head
            }
            a.next = merge(a.next.take(), Some(b));
            Some(a)
        }
    }
}

List is an alias for Option<Box<ListNode>>, so a whole list is one value that is None when empty. The first arm, (None, rest) | (rest, None) => rest, handles an empty list on either side: the other list is the answer. In the second arm, mem::swap makes a the list with the smaller front. Then a’s node stays at the front, and its next becomes the merge of the rest of a with b. No node is allocated; the boxes move.

Listing C.16 Two ways to split the lists (lines 24 to 47).

fn merge_k(mut lists: Vec<List>) -> List {
    match lists.len() {
        0 => None,
        1 => lists.pop().unwrap(),
        n => {
            let right = lists.split_off(n / 2); // lists = left half
            merge(merge_k(lists), merge_k(right))
        }
    }
}

// Merge k sorted lists using divide and conquer without heap allocation
fn merge_k_slice(lists: &mut [List]) -> List {
    match lists.len() {
        0 => None,
        1 => lists[0].take(),
        _ => {
            let mid = lists.len() / 2;
            let (left, right) = lists.split_at_mut(mid);
            merge(merge_k_slice(left), merge_k_slice(right))
        }
    }
}

merge_k splits the vector with split_off(n / 2), which moves the second half into a new Vec. That allocates a new vector at every level of the recursion.

merge_k_slice works on a slice, &mut [List], and splits it with split_at_mut, the method from section C.3. Splitting a slice only creates two views of the same memory, so this version allocates nothing to split.

Listing C.17 Building a list front to back (lines 49 to 68).

// Helper: build a list from a Vec, front to back
fn from_vec(v: Vec<i32>) -> List {
    let mut head = None;
    let mut tail = &mut head; // points to the empty slot at the end

    for val in v {
        let node = Box::new(ListNode { val, next: None });
        tail = &mut tail.insert(node).next; // fill the slot, move to the new node's next
    }

    head
}

from_vec builds the list front to back, with a slot pointer like listing C.4. tail = &mut tail.insert(node).next fills the empty slot and moves tail to the new node’s next slot.

The complete program is listing C.28 at the end of the chapter.

main merges the sample lists with merge_k, tries three edge cases, then merges the same lists again with merge_k_slice. Both versions give the same result.

$ cargo run --bin merge_k_sorted_lists_recursion
[1, 1, 2, 3, 4, 4, 5, 6]
[]
[]
[7]
[1, 1, 2, 3, 4, 4, 5, 6]

The last version keeps only the slice-based recursion:

Its node holds an i32 named val, and List is the alias for a whole list:

use std::mem;

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

type List = Option<Box<ListNode>>;

Listing C.18 The merge and the recursion on a slice (lines 11 to 34). src/bin/merge_k_sorted_lists_halves.rs

fn merge(a: List, b: List) -> List {
    match (a, b) {
        (None, rest) | (rest, None) => rest,
        (Some(mut left), Some(mut right)) => {
            if left.val > right.val {
                mem::swap(&mut left, &mut right);
            }
            left.next = merge(left.next.take(), Some(right));
            Some(left)
        }
    }
}

fn merge_k_slice(lists: &mut [List]) -> List {
    match lists.len() {
        0 => None,
        1 => lists[0].take(),
        _ => {
            let mid = lists.len() / 2;
            let (left_half, right_half) = lists.split_at_mut(mid);
            merge(merge_k_slice(left_half), merge_k_slice(right_half))
        }
    }
}

create_list builds front to back with the slot pointer, advancing it with if let Some(node) = tail. print_list collects the values as strings and joins them with " -> ".

$ cargo run --bin merge_k_sorted_lists_halves
Input lists:
[1 -> 4 -> 5]
[1 -> 3 -> 4]
[2 -> 6]

Merged list:
[1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6]

Both recursive merges recurse once for each node of their output. For short lists that is fine. For lists with hundreds of thousands of nodes, the iterative merges of sections C.3 and C.4 are safer.

C.9 The eleven versions side by side

In the table, N is the total number of nodes and k the number of lists. The extra memory column counts memory beyond the input Vec and the nodes. The stack column is the deepest the call stack goes, in frames.

• Time. Every version merges in rounds or halves, so each node moves about log2 k times: O(N log k). The “one at a time” strategy of figure C.2 would be O(kN). No version here uses it.
• Extra memory. The heap holds one entry per list: O(k). split_off makes a new Vec for each right half, so the recursion holds O(k) of them. The queue reuses the input Vec’s buffer: VecDeque::from a Vec does not reallocate.
• Stack. A recursive merge makes one call per node of its output. The last merge outputs all N nodes, so the stack reaches O(N) frames. In section 9.6, a recursive drop overflowed the 8 MiB main-thread stack between 260,000 and 270,000 nodes.
• Allocations. A dummy node costs one allocation per merge, k - 1 in total. The enum versions free a box and allocate a new one for every node they move, about N log k in all. The tail-slot version allocates nothing.

C.10 The complete files

Each file below is shown whole, in the order the chapter used it.

Listing C.19 First version: split_at_mut and a dummy head. src/bin/merge_k_sorted_lists_divide.rs

struct MergeKSorted {}

#[derive(Default)]
struct ListNode {
    data: u32,
    next: Option<Box<ListNode>>,
}
impl ListNode {
    fn new(data: u32) -> Self {
        Self { data, next: None }
    }
}

type OptionalLink<T> = Option<Box<T>>;

impl MergeKSorted {
    pub fn merge_k_lists(mut lists: Vec<OptionalLink<ListNode>>) -> OptionalLink<ListNode> {
        if lists.is_empty() {
            return None;
        }

        let (n, mut interval) = (lists.len(), 1);
        while interval < n {
            let mut i = 0;
            while i + interval < n {
                let (left, right) = lists.split_at_mut(i + interval);
                left[i] = Self::merge_two(&mut left[i], &mut right[0]);
                i += interval * 2;
            }
            interval *= 2;
        }

        lists[0].take()
    }

    fn merge_two(
        left: &mut OptionalLink<ListNode>,
        right: &mut OptionalLink<ListNode>,
    ) -> OptionalLink<ListNode> {
        let mut dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;

        while let (Some(l), Some(r)) = (left.as_ref(), right.as_ref()) {
            let smaller = if l.data < r.data {
                &mut *left
            } else {
                &mut *right
            };
            let mut head = smaller.take().unwrap();
            *smaller = head.next.take();
            tail.next = Some(head);
            tail = tail.next.as_mut().unwrap();
        }

        tail.next = left.take().or(right.take());
        dummy.next
    }
}

/// Build a list from a slice, front to back.
fn from_slice(values: &[u32]) -> OptionalLink<ListNode> {
    let mut head = None;
    for &value in values.iter().rev() {
        let mut node = Box::new(ListNode::new(value));
        node.next = head;
        head = Some(node);
    }
    head
}

/// Collect a list's values into a vector.
fn to_vec(mut list: &OptionalLink<ListNode>) -> Vec<u32> {
    let mut values = Vec::new();
    while let Some(node) = list {
        values.push(node.data);
        list = &node.next;
    }
    values
}

fn main() {
    let lists = vec![
        from_slice(&[1, 4, 5]),
        from_slice(&[1, 3, 4]),
        from_slice(&[2, 6]),
    ];
    let merged = MergeKSorted::merge_k_lists(lists);
    println!("{:?}", to_vec(&merged));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn merges_three_lists() {
        let lists = vec![
            from_slice(&[1, 4, 5]),
            from_slice(&[1, 3, 4]),
            from_slice(&[2, 6]),
        ];
        let merged = MergeKSorted::merge_k_lists(lists);
        assert_eq!(to_vec(&merged), vec![1, 1, 2, 3, 4, 4, 5, 6]);
    }

    #[test]
    fn handles_empty_input_and_empty_lists() {
        assert!(MergeKSorted::merge_k_lists(vec![]).is_none());
        let merged = MergeKSorted::merge_k_lists(vec![None, from_slice(&[2]), None]);
        assert_eq!(to_vec(&merged), vec![2]);
    }

    #[test]
    fn handles_an_odd_number_of_lists() {
        let lists: Vec<_> = (0..5)
            .map(|i| from_slice(&[i, i + 10]))
            .collect();
        let merged = MergeKSorted::merge_k_lists(lists);
        assert_eq!(to_vec(&merged), vec![0, 1, 2, 3, 4, 10, 11, 12, 13, 14]);
    }
}

Listing C.20 Take the right list out first. src/bin/merge_k_sorted_lists_swap.rs

struct MergeKSorted {}

#[derive(Default)]
struct ListNode {
    data: u32,
    next: Option<Box<ListNode>>,
}
impl ListNode {
    fn new(data: u32) -> Self {
        Self { data, next: None }
    }
}

type OptionalLink<T> = Option<Box<T>>;

impl MergeKSorted {
    pub fn merge_k_lists(mut lists: Vec<OptionalLink<ListNode>>) -> OptionalLink<ListNode> {
        if lists.is_empty() {
            return None;
        }

        let (n, mut interval) = (lists.len(), 1);
        while interval < n {
            let mut i = 0;
            while i + interval < n {
                let mut right = lists[i + interval].take();
                lists[i] = Self::merge_two(&mut lists[i], &mut right);
                i += interval * 2;
            }
            interval *= 2;
        }

        lists[0].take()
    }

    fn merge_two(
        left: &mut OptionalLink<ListNode>,
        right: &mut OptionalLink<ListNode>,
    ) -> OptionalLink<ListNode> {
        let mut dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;

        while let (Some(l), Some(r)) = (&left, &right) {
            if r.data < l.data {
                std::mem::swap(left, right);
            }
            let mut smallest = left.take().unwrap();
            *left = smallest.next.take();
            tail.next = Some(smallest);
            tail = tail.next.as_mut().unwrap();
        }

        tail.next = left.take().or(right.take());
        dummy.next
    }
}

/// Build a list from a slice, front to back.
fn from_slice(values: &[u32]) -> OptionalLink<ListNode> {
    let mut head = None;
    for &value in values.iter().rev() {
        let mut node = Box::new(ListNode::new(value));
        node.next = head;
        head = Some(node);
    }
    head
}

/// Collect a list's values into a vector.
fn to_vec(mut list: &OptionalLink<ListNode>) -> Vec<u32> {
    let mut values = Vec::new();
    while let Some(node) = list {
        values.push(node.data);
        list = &node.next;
    }
    values
}

fn main() {
    let lists = vec![
        from_slice(&[1, 4, 5]),
        from_slice(&[1, 3, 4]),
        from_slice(&[2, 6]),
    ];
    let merged = MergeKSorted::merge_k_lists(lists);
    println!("{:?}", to_vec(&merged));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn merges_three_lists() {
        let lists = vec![
            from_slice(&[1, 4, 5]),
            from_slice(&[1, 3, 4]),
            from_slice(&[2, 6]),
        ];
        let merged = MergeKSorted::merge_k_lists(lists);
        assert_eq!(to_vec(&merged), vec![1, 1, 2, 3, 4, 4, 5, 6]);
    }

    #[test]
    fn handles_empty_input_and_empty_lists() {
        assert!(MergeKSorted::merge_k_lists(vec![]).is_none());
        let merged = MergeKSorted::merge_k_lists(vec![None, from_slice(&[2]), None]);
        assert_eq!(to_vec(&merged), vec![2]);
    }

    #[test]
    fn handles_an_odd_number_of_lists() {
        let lists: Vec<_> = (0..5)
            .map(|i| from_slice(&[i, i + 10]))
            .collect();
        let merged = MergeKSorted::merge_k_lists(lists);
        assert_eq!(to_vec(&merged), vec![0, 1, 2, 3, 4, 10, 11, 12, 13, 14]);
    }
}

Listing C.21 Owned lists, no dummy node. src/bin/merge_k_sorted_lists_simple.rs

struct ListNode {
    data: u32,
    next: Link,
}

type Link = Option<Box<ListNode>>;

fn merge_k_lists(mut lists: Vec<Link>) -> Link {
    if lists.is_empty() {
        return None;
    }

    let (n, mut interval) = (lists.len(), 1);
    while interval < n {
        let mut i = 0;
        while i + interval < n {
            let left = lists[i].take();
            let right = lists[i + interval].take();
            lists[i] = merge_two(left, right);
            i += interval * 2;
        }
        interval *= 2;
    }

    lists[0].take()
}

fn merge_two(mut left: Link, mut right: Link) -> Link {
    let mut merged = None;
    let mut tail = &mut merged;

    while let (Some(l), Some(r)) = (&left, &right) {
        if r.data < l.data {
            std::mem::swap(&mut left, &mut right);
        }
        *tail = left; // hang left list on the tail
        tail = &mut tail.as_mut().unwrap().next; // step past its first node
        left = tail.take(); // cut the rest off again
    }

    *tail = left.or(right);
    merged
}

fn from_slice(values: &[u32]) -> Link {
    let mut head = None;
    for &data in values.iter().rev() {
        head = Some(Box::new(ListNode { data, next: head }));
    }
    head
}

fn to_vec(mut list: &Link) -> Vec<u32> {
    let mut values = Vec::new();
    while let Some(node) = list {
        values.push(node.data);
        list = &node.next;
    }
    values
}

fn main() {
    let lists = vec![
        from_slice(&[1, 4, 5]),
        from_slice(&[1, 3, 4]),
        from_slice(&[2, 6]),
    ];
    println!("{:?}", to_vec(&merge_k_lists(lists)));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn merges_three_lists() {
        let lists = vec![
            from_slice(&[1, 4, 5]),
            from_slice(&[1, 3, 4]),
            from_slice(&[2, 6]),
        ];
        assert_eq!(to_vec(&merge_k_lists(lists)), vec![1, 1, 2, 3, 4, 4, 5, 6]);
    }

    #[test]
    fn handles_empty_input_and_empty_lists() {
        assert!(merge_k_lists(vec![]).is_none());
        let merged = merge_k_lists(vec![None, from_slice(&[2]), None]);
        assert_eq!(to_vec(&merged), vec![2]);
    }

    #[test]
    fn handles_an_odd_number_of_lists() {
        let lists: Vec<_> = (0..5)
            .map(|i| from_slice(&[i, i + 10]))
            .collect();
        assert_eq!(
            to_vec(&merge_k_lists(lists)),
            vec![0, 1, 2, 3, 4, 10, 11, 12, 13, 14]
        );
    }
}

Listing C.22 The shortest form, with Option::insert. src/bin/merge_k_sorted_list_zero_copy.rs

type NodeLink = Option<Box<Node>>;

struct Node {
    val: i32,
    next: NodeLink,
}

fn merge_two(mut left: NodeLink, mut right: NodeLink) -> NodeLink {
    let mut dummy = Box::new(Node { val: 0, next: None });
    let mut tail = &mut dummy;

    while let (Some(left_head), Some(right_head)) = (&left, &right) {
        let smaller = if left_head.val <= right_head.val {
            &mut left
        } else {
            &mut right
        };
        let mut node = smaller.take().unwrap(); // safe: checked by while let
        *smaller = node.next.take();
        tail = tail.next.insert(node);
    }

    tail.next = if left.is_some() { left } else { right };
    dummy.next
}

fn merge_k(mut lists: Vec<NodeLink>) -> NodeLink {
    if lists.is_empty() {
        return None;
    }

    let list_count = lists.len();
    let mut gap = 1;
    while gap < list_count {
        let mut index = 0;
        while index + gap < list_count {
            let left = lists[index].take();
            let right = lists[index + gap].take();
            lists[index] = merge_two(left, right);
            index += gap * 2;
        }
        gap *= 2;
    }
    lists[0].take()
}

fn build(values: &[i32]) -> NodeLink {
    let mut head = None;
    for &val in values.iter().rev() {
        head = Some(Box::new(Node { val, next: head }));
    }
    head
}

fn print(mut current: &NodeLink) {
    while let Some(node) = current {
        print!("{} ", node.val);
        current = &node.next;
    }
    println!();
}

fn main() {
    let lists = vec![
        build(&[1, 4, 7]),
        build(&[2, 5, 8]),
        build(&[0, 3, 6, 9]),
        None,
    ];
    print(&merge_k(lists)); // 0 1 2 3 4 5 6 7 8 9

    print(&merge_k(vec![build(&[1, 1, 5]), build(&[1, 3])])); // 1 1 1 3 5
    print(&merge_k(vec![])); // (empty line)

    let five = vec![
        build(&[9]),
        build(&[1, 5]),
        build(&[3]),
        build(&[2, 8]),
        build(&[4]),
    ];
    print(&merge_k(five)); // 1 2 3 4 5 8 9
}

Listing C.23 The lists swapped by value. src/bin/merge_k_sorted_lists_owned.rs

//! Merge k sorted lists: the gap loop, and a merge that swaps the two lists by
//! value so that `left` always holds the smaller front node.

type Link = Option<Box<Node>>;

struct Node {
    val: i32,
    next: Link,
}

/// Merge two sorted lists. O(n) time, O(1) extra memory.
fn merge_two(mut left: Link, mut right: Link) -> Link {
    let mut dummy = Box::new(Node { val: 0, next: None });
    let mut tail = &mut dummy;

    while let (Some(l), Some(r)) = (&left, &right) {
        if r.val < l.val {
            (left, right) = (right, left); // left now holds the smaller front
        }
        let mut node = left.unwrap(); // safe: checked by while let
        left = node.next.take();
        tail = tail.next.insert(node);
    }

    tail.next = left.or(right);
    dummy.next
}

/// Merge k sorted lists in place: round 1 merges lists 1 apart, round 2 lists
/// 2 apart, and so on. O(N log k) time, O(1) extra memory.
fn merge_k(mut lists: Vec<Link>) -> Link {
    if lists.is_empty() {
        return None;
    }

    let size = lists.len();
    let mut gap = 1;
    while gap < size {
        let mut i = 0;
        while i + gap < size {
            lists[i] = merge_two(lists[i].take(), lists[i + gap].take());
            i += gap * 2;
        }
        gap *= 2;
    }
    lists[0].take()
}

fn build(values: &[i32]) -> Link {
    let mut head = None;
    for &val in values.iter().rev() {
        head = Some(Box::new(Node { val, next: head }));
    }
    head
}

fn to_vec(mut current: Link) -> Vec<i32> {
    let mut out = Vec::new();
    while let Some(node) = current {
        out.push(node.val);
        current = node.next;
    }
    out
}

fn main() {
    let lists = vec![
        build(&[1, 4, 7]),
        build(&[2, 5, 8]),
        build(&[0, 3, 6, 9]),
        None,
    ];
    println!("{:?}", to_vec(merge_k(lists))); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    println!(
        "{:?}",
        to_vec(merge_k(vec![build(&[1, 1, 5]), build(&[1, 3])]))
    ); // [1, 1, 1, 3, 5]
    println!("{:?}", to_vec(merge_k(vec![]))); // []
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn merges_two_lists_keeping_duplicates() {
        let merged = merge_two(build(&[1, 1, 5]), build(&[1, 3]));
        assert_eq!(to_vec(merged), vec![1, 1, 1, 3, 5]);
    }

    #[test]
    fn merges_with_empty_lists() {
        assert_eq!(to_vec(merge_two(None, build(&[2, 4]))), vec![2, 4]);
        assert_eq!(to_vec(merge_two(build(&[2, 4]), None)), vec![2, 4]);
        assert!(merge_two(None, None).is_none());
        assert!(merge_k(vec![]).is_none());
        assert!(merge_k(vec![None, None]).is_none());
    }

    #[test]
    fn merges_an_odd_number_of_lists() {
        let five = vec![
            build(&[9]),
            build(&[1, 5]),
            build(&[3]),
            build(&[2, 8]),
            build(&[4]),
        ];
        assert_eq!(to_vec(merge_k(five)), vec![1, 2, 3, 4, 5, 8, 9]);
    }

    #[test]
    fn merges_many_long_lists() {
        let lists: Vec<Link> = (0..7)
            .map(|k| {
                build(
                    &(0..100)
                        .map(|i| i * 7 + k)
                        .collect::<Vec<_>>(),
                )
            })
            .collect();
        let expected: Vec<i32> = (0..700).collect();
        assert_eq!(to_vec(merge_k(lists)), expected);
    }
}

Listing C.24 An enum node with its own take. src/bin/merge_k_sorted_lists_enum.rs

use ListNode::{Empty, Node};

type LinkTo<T> = Box<T>;

enum ListNode {
    Node { data: u32, next: LinkTo<ListNode> },
    Empty,
}

impl ListNode {
    fn take(&mut self) -> ListNode {
        std::mem::replace(self, Empty)
    }
}

struct MergeKSorted {}

impl MergeKSorted {
    pub fn merge_k_lists(mut lists: Vec<ListNode>) -> ListNode {
        if lists.is_empty() {
            return Empty;
        }

        let (n, mut interval) = (lists.len(), 1);
        while interval < n {
            let mut i = 0;
            while i + interval < n {
                let (left, right) = lists.split_at_mut(i + interval);
                left[i] = Self::merge_two(&mut left[i], &mut right[0]);
                i += interval * 2;
            }
            interval *= 2;
        }

        lists[0].take()
    }

    fn merge_two(left: &mut ListNode, right: &mut ListNode) -> ListNode {
        let mut left = left.take();
        let mut right = right.take();
        let mut merged = Empty;
        let mut tail = &mut merged;

        loop {
            let smaller = match (&left, &right) {
                (Empty, _) => {
                    *tail = right;
                    break;
                }
                (_, Empty) => {
                    *tail = left;
                    break;
                }
                (Node { data: l, .. }, Node { data: r, .. }) => {
                    if l <= r {
                        &mut left
                    } else {
                        &mut right
                    }
                }
            };

            if let Node { data, next } = smaller.take() {
                *smaller = *next;
                *tail = Node {
                    data,
                    next: LinkTo::new(Empty),
                };
                if let Node { next, .. } = tail {
                    tail = next;
                }
            }
        }

        merged
    }
}

fn main() {
    let mut lists = Vec::new();
    for values in [vec![1, 4, 5], vec![1, 3, 4], vec![2, 6]] {
        let mut head = Empty;
        for data in values.into_iter().rev() {
            head = Node {
                data,
                next: LinkTo::new(head),
            };
        }
        lists.push(head);
    }

    let merged = MergeKSorted::merge_k_lists(lists);

    let mut current = &merged;
    while let Node { data, next } = current {
        print!("{data} ");
        current = next;
    }
    println!();
}

Listing C.25 An enum with standard traits and a recursive merge. src/bin/merge_k_sorted_lists_enum_recursive.rs

pub type NodeLink = Box<ListNode>;

#[derive(Debug, PartialEq, Eq, Default)]
pub enum ListNode {
    #[default]
    Empty,
    Node(i32, NodeLink),
}

impl From<Vec<i32>> for NodeLink {
    fn from(vec: Vec<i32>) -> Self {
        vec.into_iter()
            .rev()
            .fold(NodeLink::default(), |acc, v| {
                NodeLink::new(ListNode::Node(v, acc))
            })
    }
}

impl From<Vec<i32>> for ListNode {
    fn from(vec: Vec<i32>) -> Self {
        *NodeLink::from(vec)
    }
}

impl ListNode {
    pub fn merge_k_lists(mut lists: Vec<NodeLink>) -> NodeLink {
        if lists.is_empty() {
            return NodeLink::default();
        }
        let mut interval = 1;
        while interval < lists.len() {
            for i in (0..lists.len()).step_by(interval * 2) {
                if i + interval < lists.len() {
                    let right = std::mem::take(&mut lists[i + interval]);
                    let left = std::mem::take(&mut lists[i]);
                    lists[i] = NodeLink::new(Self::merge(*left, *right));
                }
            }
            interval *= 2;
        }
        lists.swap_remove(0)
    }

    fn merge(l1: ListNode, l2: ListNode) -> ListNode {
        match (l1, l2) {
            (ListNode::Empty, l) | (l, ListNode::Empty) => l,
            (ListNode::Node(v1, n1), ListNode::Node(v2, n2)) => {
                if v1 <= v2 {
                    let rest = Self::merge(*n1, ListNode::Node(v2, n2));
                    ListNode::Node(v1, NodeLink::new(rest))
                } else {
                    let rest = Self::merge(ListNode::Node(v1, n1), *n2);
                    ListNode::Node(v2, NodeLink::new(rest))
                }
            }
        }
    }
}

fn main() {
    let lists: Vec<NodeLink> = vec![
        vec![1, 4, 5].into(),
        vec![1, 3, 4].into(),
        vec![2, 6].into(),
    ];

    let merged = ListNode::merge_k_lists(lists);

    println!("{:#?}", merged);
}

Listing C.26 A queue of lists. src/bin/merge_k_sorted_lists_pairs.rs

use std::collections::VecDeque;

struct ListNode {
    data: u32,
    next: Option<Box<ListNode>>,
}

type Link = Option<Box<ListNode>>;

fn merge_k_lists(lists: Vec<Link>) -> Link {
    let mut queue: VecDeque<Link> = lists.into();
    while queue.len() > 1 {
        let a = queue.pop_front().unwrap();
        let b = queue.pop_front().unwrap();
        queue.push_back(merge_two(a, b));
    }
    queue.pop_front().flatten()
}

fn merge_two(mut a: Link, mut b: Link) -> Link {
    let mut dummy = Box::new(ListNode {
        data: 0,
        next: None,
    });
    let mut tail = &mut dummy;

    while let (Some(x), Some(y)) = (&a, &b) {
        let pick = if x.data <= y.data { &mut a } else { &mut b };
        let mut node = pick.take().unwrap();
        *pick = node.next.take();
        tail = tail.next.insert(node);
    }
    tail.next = a.or(b);
    dummy.next
}

fn main() {
    let mut lists = Vec::new();
    for values in [vec![1, 4, 5], vec![1, 3, 4], vec![2, 6]] {
        let mut head = None;
        for data in values.into_iter().rev() {
            head = Some(Box::new(ListNode { data, next: head }));
        }
        lists.push(head);
    }

    let mut cur = merge_k_lists(lists);
    while let Some(node) = cur {
        print!("{} ", node.data);
        cur = node.next;
    }
    println!();
}

Listing C.27 A heap of list heads. src/bin/merge_k_sorted_lists_heap.rs

use std::{cmp::Reverse, collections::BinaryHeap};

struct ListNode {
    data: u32,
    next: Option<Box<ListNode>>,
}

type Link = Option<Box<ListNode>>;

fn merge_k_lists(mut lists: Vec<Link>) -> Link {
    let mut heap = BinaryHeap::new();
    for (i, list) in lists.iter().enumerate() {
        if let Some(node) = list {
            heap.push(Reverse((node.data, i)));
        }
    }

    let mut dummy = Box::new(ListNode {
        data: 0,
        next: None,
    });
    let mut tail = &mut dummy;

    while let Some(Reverse((_, i))) = heap.pop() {
        let mut node = lists[i].take().unwrap();
        lists[i] = node.next.take();
        if let Some(next) = &lists[i] {
            heap.push(Reverse((next.data, i)));
        }
        tail = tail.next.insert(node);
    }
    dummy.next
}

fn main() {
    let mut lists = Vec::new();
    for values in [vec![1, 4, 5], vec![1, 3, 4], vec![2, 6]] {
        let mut head = None;
        for data in values.into_iter().rev() {
            head = Some(Box::new(ListNode { data, next: head }));
        }
        lists.push(head);
    }

    let mut cur = merge_k_lists(lists);
    while let Some(node) = cur {
        print!("{} ", node.data);
        cur = node.next;
    }
    println!();
}

Listing C.28 Recursion on halves, two ways to split. src/bin/merge_k_sorted_lists_recursion.rs

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

type List = Option<Box<ListNode>>;

// Merge two sorted lists
fn merge(a: List, b: List) -> List {
    match (a, b) {
        (None, rest) | (rest, None) => rest,
        (Some(mut a), Some(mut b)) => {
            if a.val > b.val {
                std::mem::swap(&mut a, &mut b); // a is now the smaller head
            }
            a.next = merge(a.next.take(), Some(b));
            Some(a)
        }
    }
}

// Merge k sorted lists using divide and conquer
fn merge_k(mut lists: Vec<List>) -> List {
    match lists.len() {
        0 => None,
        1 => lists.pop().unwrap(),
        n => {
            let right = lists.split_off(n / 2); // lists = left half
            merge(merge_k(lists), merge_k(right))
        }
    }
}

// Merge k sorted lists using divide and conquer without heap allocation
fn merge_k_slice(lists: &mut [List]) -> List {
    match lists.len() {
        0 => None,
        1 => lists[0].take(),
        _ => {
            let mid = lists.len() / 2;
            let (left, right) = lists.split_at_mut(mid);
            merge(merge_k_slice(left), merge_k_slice(right))
        }
    }
}

// Helper: build a list from a Vec, front to back
fn from_vec(v: Vec<i32>) -> List {
    let mut head = None;
    let mut tail = &mut head; // points to the empty slot at the end

    for val in v {
        let node = Box::new(ListNode { val, next: None });
        tail = &mut tail.insert(node).next; // fill the slot, move to the new node's next
    }

    head
}

// Helper: turn a list back into a Vec for printing
fn to_vec(mut cur: &List) -> Vec<i32> {
    let mut out = Vec::new();
    while let Some(node) = cur {
        out.push(node.val);
        cur = &node.next;
    }
    out
}

fn main() {
    let lists = vec![
        from_vec(vec![1, 4, 5]),
        from_vec(vec![1, 3, 4]),
        from_vec(vec![2, 6]),
    ];
    let merged = merge_k(lists);
    println!("{:?}", to_vec(&merged)); // [1, 1, 2, 3, 4, 4, 5, 6]

    // Edge cases
    println!("{:?}", to_vec(&merge_k(vec![]))); // []
    println!("{:?}", to_vec(&merge_k(vec![None, None]))); // []
    println!("{:?}", to_vec(&merge_k(vec![from_vec(vec![7])]))); // [7]

    // The same lists, merged by splitting a slice instead of the vector
    let mut lists = [
        from_vec(vec![1, 4, 5]),
        from_vec(vec![1, 3, 4]),
        from_vec(vec![2, 6]),
    ];
    println!("{:?}", to_vec(&merge_k_slice(&mut lists))); // [1, 1, 2, 3, 4, 4, 5, 6]
}

Listing C.29 Recursion on a slice. src/bin/merge_k_sorted_lists_halves.rs

use std::mem;

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

type List = Option<Box<ListNode>>;

fn merge(a: List, b: List) -> List {
    match (a, b) {
        (None, rest) | (rest, None) => rest,
        (Some(mut left), Some(mut right)) => {
            if left.val > right.val {
                mem::swap(&mut left, &mut right);
            }
            left.next = merge(left.next.take(), Some(right));
            Some(left)
        }
    }
}

fn merge_k_slice(lists: &mut [List]) -> List {
    match lists.len() {
        0 => None,
        1 => lists[0].take(),
        _ => {
            let mid = lists.len() / 2;
            let (left_half, right_half) = lists.split_at_mut(mid);
            merge(merge_k_slice(left_half), merge_k_slice(right_half))
        }
    }
}

fn create_list(arr: &[i32]) -> List {
    let mut head = None;
    let mut tail = &mut head;

    for &val in arr {
        *tail = Some(Box::new(ListNode { val, next: None }));
        if let Some(node) = tail {
            tail = &mut node.next;
        }
    }

    head
}

fn print_list(mut list: &List) {
    let mut elements = Vec::new();
    while let Some(node) = list {
        elements.push(node.val.to_string());
        list = &node.next;
    }
    println!("[{}]", elements.join(" -> "));
}

fn main() {
    let mut lists = vec![
        create_list(&[1, 4, 5]),
        create_list(&[1, 3, 4]),
        create_list(&[2, 6]),
    ];

    println!("Input lists:");
    for list in &lists {
        print_list(list);
    }

    let merged = merge_k_slice(&mut lists);

    println!("\nMerged list:");
    print_list(&merged);
}

Exercises

1. Write the “one at a time” merge and time it against listing C.22 on 200 lists of 5,000 nodes each.
2. Make merge_two from listing C.5 generic over any T: Ord.
3. Write a k-way merge of sorted text files with the heap strategy, keeping only one line per file in memory.
4. Count allocations in listings C.9 and C.12 with a custom global allocator that increments a counter, and confirm the difference described in section C.5.1.