Merge k sorted linked lists

You're in a Google interview, and the interviewer poses a scenario: "Imagine you have a trillion integers spread across thousands of machines. Each machine has sorted its local chunk. How do you produce one globally sorted result?" You recognize instantly that this is the k-way merge problem, one of the most practical algorithms in distributed computing. It's also a favorite interview question at Google, Amazon, and Databricks, and it is commonly known as "Merge k Sorted Lists" on other platforms like LeetCode and Blind 75.

TL;DR

Use a min heap of size k to always track the smallest available node across all lists. Poll the minimum, append it to the output, and push that node's successor back into the heap. This runs in O(n * k * log(k)) time and O(k) space, beating the brute-force O(N log N) sort approach. Java's PriorityQueue with a custom comparator makes the implementation clean and concise.

Why This Problem Matters

Merging k sorted linked lists sits at the intersection of two fundamental data structures: linked lists and heaps. I've seen this problem used as the main course in interviews, not just a warm-up. It tests whether you can identify the right data structure for the job and then wire it up correctly with pointer manipulation. The underlying algorithm powers external sorting in databases, merge phases in MapReduce, and LSM-tree compaction in systems like Cassandra and RocksDB.

Setting Up the Problem

Given a list of k sorted linked lists of average length n, write a method to merge them into a single globally sorted linked list.

Constraints:

• 0 < k, n < 10,000
• Target runtime: O(n * k * log(k))
• Target space: O(k)

Here's our example input, three sorted linked lists:

After merging, the output should be:

The result is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], a single sorted linked list containing every element from all three inputs.

Edge Cases to Consider

1. Null heads in the input: Some lists may be empty
2. Single-element lists: A list with just one node
3. Duplicate values across lists: Multiple lists containing the same value
4. Vastly different lengths: One list with 1 element, another with 10,000

Why a Min Heap?

The naive approach would be to dump all values into an array and sort. That gives O(N log N) time where N = n * k. Can we do better?

Think about it this way: at any point during the merge, we only care about the smallest element among the current heads of all k lists. We don't need to look at every element, just the k candidates at the front of each list.

A min heap is purpose-built for this. It maintains the minimum element at the top and supports insertion and extraction in O(log k) time. Since we process N total elements and each one enters and leaves the heap exactly once, the total time is O(N log k), which equals O(n * k * log(k)).

The Algorithm

1. Seed the heap: Add the head node of each non-null list to the min heap
2. Poll and link: Extract the minimum node, append it to the output list
3. Push the successor: If the polled node has a next pointer, push it into the heap
4. Repeat until the heap is empty

Here's what the heap looks like after seeding it with the three head nodes (0, 1, 2):

We poll 0 (from L3), append it to our output, and push 3 (the next node in L3) into the heap:

The heap re-heapifies so that 1 (the new minimum) bubbles to the top. This process repeats for every element.

Watching the Output Build

Each poll appends one node to the output. The heap always has at most k elements, so each operation is O(log k).

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution {
  public ListNode mergeLists(List<ListNode> lists) {
    // Create a min heap ordered by node data
    PriorityQueue<ListNode> minHeap =
      new PriorityQueue<>(Comparator.comparingInt(l -> l.data));

    // Seed the heap with all non-null head nodes
    for (ListNode listNode : lists) {
      if (listNode != null) minHeap.offer(listNode);
    }

    // Dummy head simplifies output list construction
    ListNode dummyHead = new ListNode(0), iterator = dummyHead;

    while (!minHeap.isEmpty()) {
      // Poll the node with the smallest data value
      ListNode node = minHeap.poll();

      // Append it to the output list
      iterator.next = node;

      // If this node has a successor, push it into the heap
      if (node.next != null) minHeap.offer(node.next);

      // Advance the output iterator
      iterator = iterator.next;
    }

    return dummyHead.next;
  }
}

Let's trace through the first few iterations with our example input [[1,4], [2,5,6,7,9], [0,3,8,10]]:

Initialization:

• Heap seeded with heads: 2 (from L3, L1, L2)
• Output: dummy -> (empty)

Iteration 1:

• Poll 0 (L3). Output: [0]. Push 3 (next in L3). Heap: 2

Iteration 2:

• Poll 1 (L1). Output: [0, 1]. Push 4 (next in L1). Heap: 4

Iteration 3:

• Poll 2 (L2). Output: [0, 1, 2]. Push 5 (next in L2). Heap: 5

This continues until all 11 elements have been polled and linked together.

The Dummy Head Pattern

Notice the dummyHead trick. Without it, you'd need an if check on every iteration to handle the first node differently from subsequent nodes. The dummy node absorbs that complexity: every node gets appended the same way, and you return dummyHead.next to skip the placeholder.

This pattern shows up in almost every linked list construction problem. If you're not using it already, add it to your toolkit.

Complexity Analysis

Time Complexity: O(n * k * log(k))

Every element across all k lists enters the heap once and leaves once. Each heap operation (offer/poll) costs O(log k) because the heap never exceeds size k. With N = n * k total elements:

• Total heap operations: 2N (one offer + one poll per element)
• Cost per operation: O(log k)
• Total: O(N log k) = O(n * k * log(k))

Space Complexity: O(k)

The heap stores at most k nodes at any time, one per list. We reuse existing ListNode objects for the output rather than creating new nodes, so the only extra allocation is the heap itself.

Compare this with the brute-force approach: O(n * k) space to collect all values, plus O(n * k * log(n * k)) time to sort them. The heap approach wins on both fronts.

Alternative Approaches

1. Divide and conquer: Pair up lists and merge each pair, then repeat. Same O(N log k) time, O(1) extra space if done iteratively. More complex to implement.
2. Brute force sort: Collect all values, sort, rebuild the list. O(N log N) time, O(N) space. Simpler but slower.
3. Sequential two-at-a-time merge: Merge list 1 with list 2, then result with list 3, etc. O(N * k) time, which is worse when k is large.

The min heap approach hits the sweet spot of optimal time complexity with a clean, straightforward implementation.

Common Pitfalls

1. Forgetting to check for null heads: Not every list in the input will be non-empty. Always guard with if (listNode != null) before offering to the heap.

2. Not pushing the successor: After polling a node, you must check node.next and push it. Missing this causes the algorithm to only process head nodes.

3. Comparator mistakes: Java's PriorityQueue is a min heap by default, but only for Comparable types. ListNode is not comparable, so you need an explicit comparator. Forgetting this leads to a ClassCastException at runtime.

4. Returning dummyHead instead of dummyHead.next: The dummy is a placeholder with value 0. The real output starts at its next pointer.

Interview Tips

When you encounter this problem:

1. Start by identifying the data structure: The moment you hear "k sorted" and "merge," think heap. Mention that a min heap of size k lets you always pick the global minimum efficiently.

2. Discuss complexity before coding: "I'll use a min heap of size k. Each of the N total elements does one push and one poll at O(log k) each, giving O(N log k) total. Space is O(k) for the heap." This shows you understand why the approach works, not just how.

3. Mention the divide-and-conquer alternative: Even if you implement the heap solution, knowing that you could also pair-merge lists in rounds demonstrates breadth of knowledge.

4. Draw the heap state: Sketch two or three iterations showing which node gets polled and which gets pushed. This catches errors before you write a single line of code.

5. Watch for the follow-up: "What if the lists were on different machines?" This leads to a discussion of external sorting, distributed merge, and network I/O. The core algorithm stays the same; the challenge becomes minimizing data transfer.

Solutions in Other Languages

Python

Python's heapq module provides a min heap, but ListNode objects are not directly comparable. We create a ListNodeCmp wrapper that implements __lt__ and __le__ so heapq can compare nodes by their data values.

import heapq
from typing import List
from ListNode import ListNode


class ListNodeCmp(ListNode):
    def __init__(self, node: ListNode):
        super().__init__(node.data, node.next)

    def __lt__(self, other):
        return self.data < other.data

    def __le__(self, other):
        return self.data <= other.data


class Solution:
    def merge_lists(self, lists: List[ListNode]) -> ListNode:
        heap_items = []
        heapq.heapify(heap_items)
        for node in lists:
            if node is not None:
                heapq.heappush(heap_items, ListNodeCmp(node))
        dummy_head = ListNodeCmp(ListNode(0))
        iterator = dummy_head
        while len(heap_items) > 0:
            node = heapq.heappop(heap_items)
            iterator.next = node
            if node.next is not None:
                heapq.heappush(heap_items, ListNodeCmp(node.next))
            iterator = iterator.next
        return dummy_head.next

JavaScript

JavaScript has no built-in heap, so we implement a MinHeap class that orders ListNode objects by their data field.

class MinHeap {
  constructor() {
    this.heap = [];
  }

  offer(node) {
    this.heap.push(node);
    this.bubbleUp(this.heap.length - 1);
  }

  poll() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index].data >= this.heap[parentIndex].data) break;
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    while (true) {
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;
      let smallest = index;
      if (leftChild < this.heap.length && this.heap[leftChild].data < this.heap[smallest].data) {
        smallest = leftChild;
      }
      if (rightChild < this.heap.length && this.heap[rightChild].data < this.heap[smallest].data) {
        smallest = rightChild;
      }
      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

class Solution {
  mergeLists(lists) {
    const minHeap = new MinHeap();
    for (const listNode of lists) {
      if (listNode !== null) minHeap.offer(listNode);
    }
    const dummyHead = new ListNode(0);
    let iterator = dummyHead;
    while (!minHeap.isEmpty()) {
      const node = minHeap.poll();
      iterator.next = node;
      if (node.next !== null) minHeap.offer(node.next);
      iterator = iterator.next;
    }
    return dummyHead.next;
  }
}

TypeScript

Same approach as JavaScript, with type annotations on the MinHeap class.

class MinHeap {
  private heap: ListNode[];

  constructor() {
    this.heap = [];
  }

  offer(node: ListNode): void {
    this.heap.push(node);
    this.bubbleUp(this.heap.length - 1);
  }

  poll(): ListNode | null {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop()!;
    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown(0);
    return min;
  }

  isEmpty(): boolean {
    return this.heap.length === 0;
  }

  private bubbleUp(index: number): void {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index].data >= this.heap[parentIndex].data) break;
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  private bubbleDown(index: number): void {
    while (true) {
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;
      let smallest = index;
      if (leftChild < this.heap.length && this.heap[leftChild].data < this.heap[smallest].data) {
        smallest = leftChild;
      }
      if (rightChild < this.heap.length && this.heap[rightChild].data < this.heap[smallest].data) {
        smallest = rightChild;
      }
      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

class Solution {
  mergeLists(lists: (ListNode | null)[]): ListNode | null {
    const minHeap = new MinHeap();
    for (const listNode of lists) {
      if (listNode !== null) minHeap.offer(listNode);
    }
    const dummyHead = new ListNode(0);
    let iterator: ListNode = dummyHead;
    while (!minHeap.isEmpty()) {
      const node = minHeap.poll()!;
      iterator.next = node;
      if (node.next !== null) minHeap.offer(node.next);
      iterator = iterator.next;
    }
    return dummyHead.next;
  }
}

C++

C++ uses priority_queue with a custom comparator struct. Note the reversed comparison (a->data > b->data) since priority_queue is a max heap by default.

#include <vector>
#include <queue>

using namespace std;

struct ListNodeComparator {
  bool operator()(ListNode* a, ListNode* b) {
    return a->data > b->data;
  }
};

class Solution {
public:
  ListNode* mergeLists(vector<ListNode*> lists) {
    priority_queue<ListNode*, vector<ListNode*>, ListNodeComparator> minHeap;
    for (ListNode* listNode : lists) {
      if (listNode != nullptr) minHeap.push(listNode);
    }
    ListNode* dummyHead = new ListNode(0);
    ListNode* iterator = dummyHead;
    while (!minHeap.empty()) {
      ListNode* node = minHeap.top();
      minHeap.pop();
      iterator->next = node;
      if (node->next != nullptr) minHeap.push(node->next);
      iterator = iterator->next;
    }
    return dummyHead->next;
  }
};

Go

Go's container/heap package requires implementing the heap.Interface (Len, Less, Swap, Push, Pop).

import "container/heap"

type MinHeap []*ListNode

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].data < h[j].data }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
  *h = append(*h, x.(*ListNode))
}

func (h *MinHeap) Pop() interface{} {
  old := *h
  n := len(old)
  node := old[n-1]
  *h = old[0 : n-1]
  return node
}

func (s *Solution) mergeLists(lists []*ListNode) *ListNode {
  minHeap := &MinHeap{}
  heap.Init(minHeap)
  for _, listNode := range lists {
    if listNode != nil {
      heap.Push(minHeap, listNode)
    }
  }
  dummyHead := newListNode(0)
  iterator := dummyHead
  for minHeap.Len() > 0 {
    node := heap.Pop(minHeap).(*ListNode)
    iterator.next = node
    if node.next != nil {
      heap.Push(minHeap, node.next)
    }
    iterator = iterator.next
  }
  return dummyHead.next
}

Kotlin

Kotlin leverages Java's PriorityQueue with a clean lambda comparator.

import java.util.PriorityQueue
import java.util.Comparator

class Solution {
  fun mergeLists(lists: List<ListNode>): ListNode? {
    val minHeap = PriorityQueue<ListNode>(Comparator.comparingInt { it.data })
    for (listNode in lists) {
      minHeap.offer(listNode)
    }
    val dummyHead = ListNode(0)
    var iterator = dummyHead
    while (minHeap.isNotEmpty()) {
      val node = minHeap.poll()
      iterator.next = node
      if (node?.next != null) minHeap.offer(node.next)
      iterator = iterator.next!!
    }
    return dummyHead.next
  }
}

Scala

Scala uses a mutable PriorityQueue with negated ordering to simulate a min heap, since PriorityQueue is a max heap by default.

import scala.collection.mutable

class Solution {
  def mergeLists(lists: List[ListNode]): ListNode = {
    val minHeap = mutable.PriorityQueue[ListNode]()(Ordering.by(-_.data))
    lists.filter(_ != null).foreach(n => minHeap.enqueue(n))
    val dummyHead = ListNode(0)
    var iterator = dummyHead
    while (minHeap.nonEmpty) {
      val node = minHeap.dequeue
      iterator.next = node
      if (node.next != null) minHeap.enqueue(node.next)
      iterator = iterator.next
    }
    dummyHead.next
  }
}

C#

C# 10+ provides PriorityQueue<TElement, TPriority> which serves as a built-in min heap when using integer priorities.

public class Solution {
    public ListNode? MergeLists(List<ListNode> lists) {
        var minHeap = new PriorityQueue<ListNode, int>();
        foreach (var listNode in lists) {
            if (listNode != null) minHeap.Enqueue(listNode, listNode.data);
        }
        var dummyHead = new ListNode(0);
        var iterator = dummyHead;
        while (minHeap.Count > 0) {
            var node = minHeap.Dequeue();
            iterator.next = node;
            if (node.next != null) minHeap.Enqueue(node.next, node.next.data);
            iterator = iterator.next;
        }
        return dummyHead.next;
    }
}

Dart

Dart lacks a built-in priority queue, so we maintain a sorted list and use binary search insertion to keep it ordered.

ListNode? mergeLists(List<ListNode?> lists) {
  List<ListNode> minHeap = [];
  for (ListNode? node in lists) {
    if (node != null) minHeap.add(node);
  }
  minHeap.sort((a, b) => a.data.compareTo(b.data));
  ListNode dummyHead = ListNode(0);
  ListNode iterator = dummyHead;
  while (minHeap.isNotEmpty) {
    ListNode node = minHeap.removeAt(0);
    iterator.next = node;
    if (node.next != null) {
      _insertSorted(minHeap, node.next!);
    }
    iterator = iterator.next!;
  }
  return dummyHead.next;
}

void _insertSorted(List<ListNode> heap, ListNode node) {
  int low = 0;
  int high = heap.length;
  while (low < high) {
    int mid = (low + high) ~/ 2;
    if (heap[mid].data <= node.data) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  heap.insert(low, node);
}

Swift

Swift uses a simple approach of finding the minimum index in a heads array on each iteration.

func mergeLists(_ lists: [ListNode?]) -> ListNode? {
    var heads = lists.compactMap { $0 }
    let dummyHead = ListNode(0)
    var iterator = dummyHead
    while !heads.isEmpty {
        let minIndex = heads.indices.min(by: { heads[$0].data < heads[$1].data })!
        let node = heads.remove(at: minIndex)
        iterator.next = node
        if let next = node.next {
            heads.append(next)
        }
        iterator = iterator.next!
    }
    return dummyHead.next
}

Rust

Rust uses BinaryHeap with Reverse tuples to create a min heap. Ownership semantics require careful handling of node extraction and reinsertion.

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
    pub fn merge_lists(&self, lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let mut min_heap = BinaryHeap::new();
        let mut current_nodes: Vec<Option<Box<ListNode>>> = lists.into_iter().collect();
        for (index, node) in current_nodes.iter().enumerate() {
            if let Some(ref n) = node {
                min_heap.push(Reverse((n.data, index)));
            }
        }
        let mut dummy = Box::new(ListNode::new(0));
        let mut current = &mut dummy;
        while let Some(Reverse((_, index))) = min_heap.pop() {
            let node = current_nodes[index].take();
            if let Some(mut extracted) = node {
                current_nodes[index] = extracted.next.take();
                if let Some(ref next_node) = current_nodes[index] {
                    min_heap.push(Reverse((next_node.data, index)));
                }
                extracted.next = None;
                current.next = Some(extracted);
                current = current.next.as_mut().unwrap();
            }
        }
        dummy.next
    }
}

PHP

PHP's SplPriorityQueue is a max heap by default, so we negate the priority values to simulate min heap behavior.

class Solution {
    public function mergeLists(array $lists): ?ListNode {
        $minHeap = new SplPriorityQueue();
        foreach ($lists as $listNode) {
            if ($listNode !== null) $minHeap->insert($listNode, -$listNode->data);
        }
        $dummyHead = new ListNode(0);
        $iterator = $dummyHead;
        while (!$minHeap->isEmpty()) {
            $node = $minHeap->extract();
            $iterator->next = $node;
            if ($node->next !== null) $minHeap->insert($node->next, -$node->next->data);
            $iterator = $iterator->next;
        }
        return $dummyHead->next;
    }
}

Ruby

Ruby has no built-in heap, so we implement a MinHeap class with standard bubble-up and bubble-down operations.

class Solution
  def merge_lists(lists)
    min_heap = MinHeap.new
    lists.each { |node| min_heap.push(node) if node }
    dummy_head = ListNode.new(0)
    iterator = dummy_head
    while !min_heap.empty?
      node = min_heap.pop
      iterator.next = node
      min_heap.push(node.next) if node.next
      iterator = iterator.next
    end
    dummy_head.next
  end
end

class MinHeap
  def initialize
    @heap = []
  end

  def push(node)
    @heap << node
    bubble_up(@heap.size - 1)
  end

  def pop
    return nil if @heap.empty?
    min_node = @heap[0]
    last_node = @heap.pop
    if [email protected]?
      @heap[0] = last_node
      bubble_down(0)
    end
    min_node
  end

  def empty?
    @heap.empty?
  end

  private

  def bubble_up(index)
    parent_index = (index - 1) / 2
    while index > 0 && @heap[index].data < @heap[parent_index].data
      @heap[index], @heap[parent_index] = @heap[parent_index], @heap[index]
      index = parent_index
      parent_index = (index - 1) / 2
    end
  end

  def bubble_down(index)
    size = @heap.size
    loop do
      left_child = 2 * index + 1
      right_child = 2 * index + 2
      smallest = index
      if left_child < size && @heap[left_child].data < @heap[smallest].data
        smallest = left_child
      end
      if right_child < size && @heap[right_child].data < @heap[smallest].data
        smallest = right_child
      end
      break if smallest == index
      @heap[index], @heap[smallest] = @heap[smallest], @heap[index]
      index = smallest
    end
  end
end

Key Takeaways

• A min heap of size k is the optimal data structure for tracking the minimum across k sorted sources, giving O(N log k) time versus O(N log N) for a brute-force sort.
• The algorithm processes each element exactly twice (one push, one poll), and the heap never exceeds k entries, yielding O(k) space.
• The dummy head pattern eliminates special-case handling for the first output node. Use it in every linked list construction problem.
• Java's PriorityQueue requires a custom Comparator for non-Comparable types like ListNode. Forgetting this is a common runtime error.
• Always check for null heads when seeding the heap and for null successors when pushing after a poll.

Practice Makes Perfect

Once you're comfortable with k-way merge, these related problems will deepen your understanding of heaps and linked list manipulation:

• Merge two sorted linked lists (the simpler building block)
• Find the median from a data stream (two heaps working together)
• Sort a nearly sorted array (sliding window heap)
• Top k frequent elements (heap for ranking)

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed roles at top tech companies. Whether you're targeting Google, Amazon, or your next big opportunity, mastering fundamentals like k-way merge will set you apart.