Merge k Sorted Lists

Pairwise merge

Divide & conquer or min-heap. Your first ‘hard’ that’s just a clean composition of basics.

Published Apr 15, 2026

Problem

You are given an array of k sorted linked lists. Merge them into one sorted linked list and return its head.

Input

lists = [[1,4,5],[1,3,4],[2,6]]

Output

[1,1,2,3,4,4,5,6]

Input

lists = []

Output

[]

Intuition

Merge k Sorted Lists is not a new problem. It is the merge step from #21 repeated on a larger schedule.

The key question is how to schedule the merges. There are two standard answers:

keep one current node from each list in a min-heap
repeatedly merge pairs of lists until only one remains

The second one is cleaner in a linked-list implementation because it reuses the exact same merge_two_lists primitive you already know.

Approach

Pairwise Merge

TimeO(n log k)

SpaceO(1)

Recommended

Merge lists in rounds. In each round, merge list i with list i + step, where step doubles after every pass. This is the iterative version of divide and conquer:

step = 1: merge adjacent pairs
step = 2: merge the results of the previous round
repeat until one list remains

Each node participates in O(log k) merges, so the total work is O(n log k).

impl Solution {
    pub fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        fn merge_two(
            mut list1: Option<Box<ListNode>>,
            mut list2: Option<Box<ListNode>>,
        ) -> Option<Box<ListNode>> {
            let mut dummy = Box::new(ListNode { val: 0, next: None });
            let mut tail = &mut dummy;

            while list1.is_some() && list2.is_some() {
                let take_left = list1.as_ref().unwrap().val <= list2.as_ref().unwrap().val;
                let mut node= if take_left {
                    let mut node= list1.take().unwrap();
                    list1= node.next.take();
                    node
                } else {
                    let mut node= list2.take().unwrap();
                    list2= node.next.take();
                    node
                };

                tail.next= Some(node);
                tail= tail.next.as_mut().unwrap();
            }

            tail.next= if list1.is_some() { list1 } else { list2 };
            dummy.next
        }

        if lists.is_empty() {
            return None;
        }

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

        lists.into_iter().next().unwrap_or(None)
    }
}

Rust · runnable

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const mergeTwo = (list1: ListNode | null, list2: ListNode | null): ListNode | null => {
    const dummy = new ListNode(0);
    let tail = dummy;

    while (list1 !== null && list2 !== null) {
      if (list1.val <= list2.val) {
        tail.next= list1;
        list1= list1.next;
      } else {
        tail.next= list2;
        list2= list2.next;
      }
      tail= tail.next;
    }

    tail.next= list1 ?? list2;
    return dummy.next;
  };

  if (lists.length= 0) return null;

  for (let step= 1; step < lists.length; step <<= 1) {
    for (let i= 0; i + step < lists.length; i = step << 1) {
      lists[i]= mergeTwo(lists[i], lists[i + step]);
    }
  }

  return lists[0] ?? null;
}

TypeScript · runnable

Trace

Pairwise rounds for lists = [[1,4,5], [1,3,4], [2,6]]:

round	pairs merged	resulting list heads
start	—	[1,4,5], [1,3,4], [2,6]
1	0 + 1	[1,1,3,4,4,5], [2,6]
2	0 + 1	[1,1,2,3,4,4,5,6]

The same merge_two_lists primitive does all the work. The schedule is the only thing that changes.

Edge cases

No lists — return null.
One non-null list — return it unchanged.
Many empty lists — skip over null inputs naturally.
Strongly uneven lengths — pairwise merging still touches each node only O(log k) times.

Takeaway

Merge k Sorted Lists is a composition problem, not a novel one. Once merge_two_lists is solid, the hard part is deciding how to schedule repeated merges. Pairwise reduction is the cleanest path when you want a linked-list solution that stays simple in both Rust and TypeScript.

Easy#21

Merge Two Sorted Lists

Merge step of merge sort. In Rust, practice with Option<Box<ListNode>>.

Medium#143

Reorder List

Combines three techniques: find middle, reverse second half, merge.

Easy#206

Reverse Linked List