Combine Multiple Sorted Linked Lists Using a Min-Heap

You're given an array of k sorted linked lists and need to merge them into a single sorted linked list. This problem is also known as Merge K Sorted Lists on other platforms and is Meta's most frequently asked linked list question. It's a natural extension of merging two sorted lists, but scaling to k lists requires a smarter approach than pairwise comparison.

For example, given [[1,4,5], [1,3,4], [2,6]], the merged result is [1,1,2,3,4,4,5,6].

Two Approaches Worth Knowing

There are two standard O(N log k) solutions: a min-heap that always gives you the smallest available node, and divide and conquer that recursively halves the problem. Both achieve the same asymptotic complexity, but they differ in constant factors and implementation style.

The brute-force alternative (comparing all k heads on every extraction) runs in O(N * k), which becomes expensive when k is large. Both heap and divide-and-conquer reduce the per-node work from O(k) to O(log k).

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

Approach 1: Min-Heap

The idea is simple. Start by pushing the head of each list into a min-heap. The heap always surfaces the smallest node across all k lists. Extract it, append it to the result, and push that node's successor back into the heap. Repeat until the heap is empty.

Step-by-Step Trace

Let's walk through [[1,4,5], [1,3,4], [2,6]]:

The heap starts with the three heads: [1, 1, 2]. We extract 1 from List 1, push its next node 4, so the heap becomes [1, 2, 4]. Extract 1 from List 2, push 3, heap is [2, 3, 4]. Extract 2 from List 3, push 6, heap is [3, 4, 6]. This continues until all nodes are consumed.

The result:

Java Implementation (Min-Heap)

import java.util.PriorityQueue;

public class Solution {

  public ListNode mergeNLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
      return null;
    }

    PriorityQueue<ListNode> minHeap =
        new PriorityQueue<>((a, b) -> a.data - b.data);

    for (ListNode node : lists) {
      if (node != null) {
        minHeap.offer(node);
      }
    }

    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (!minHeap.isEmpty()) {
      ListNode minNode = minHeap.poll();
      current.next = minNode;
      current = current.next;

      if (minNode.next != null) {
        minHeap.offer(minNode.next);
      }
    }

    return dummy.next;
  }
}

The PriorityQueue comparator (a, b) -> a.data - b.data ensures the smallest data value is always at the top. The dummy node avoids special-casing the first insertion.

Approach 2: Divide and Conquer

Split the k lists into two halves, recursively merge each half into a single list, then merge the two resulting lists with a standard two-list merge. This mirrors merge sort's structure.

With 4 lists, the first level merges (L1, L2) and (L3, L4) independently. The second level merges those two results. Each level processes all N nodes once, and there are log(k) levels, giving O(N log k) total.

This approach is used in the JavaScript, TypeScript, Go, and Ruby solutions shown below.

Complexity Analysis

Time: O(N * log k) where N is the total number of nodes across all lists and k is the number of lists.

• Min-heap: Each of the N nodes is pushed and popped from a heap of size at most k. Each operation is O(log k).
• Divide and conquer: log(k) merge levels, each processing all N nodes in O(N).

Space: O(k) for the min-heap approach (the heap holds at most k nodes). Divide and conquer uses O(log k) stack space for recursion. Neither approach allocates new list nodes.

Edge Cases

• Empty array []: Return null immediately.
• Array with empty list [[]]: The null head is skipped, nothing enters the heap, return null.
• Single list [[1,2,3]]: Only one head enters the heap. Nodes are extracted in order. Result is the original list.
• All single-node lists [[1],[2],[3]]: Each node enters the heap exactly once. Result is sorted naturally.
• Lists of vastly different lengths: The heap handles this gracefully since shorter lists simply stop contributing nodes earlier.

Practice This Problem

Combine Multiple Sorted Linked Lists tests your ability to choose the right data structure under time pressure. The min-heap solution is concise and universal, while divide and conquer shows deeper algorithmic thinking. Try it yourself on Firecode.io where you can step through hints for both approaches.

If you're comfortable with this problem, try these next:

• Reverse a Linked List (fundamental linked list pointer manipulation)
• Subarray with Maximum Total (heap and divide-and-conquer both apply)
• Combining Overlapping Ranges (sorting + merge pattern)

Solutions in Other Languages

Python

Python's heapq module provides a min-heap, but ListNode objects aren't directly comparable. The HeapNode wrapper class defines __lt__ to enable heap ordering by node value.

import heapq

class Solution:
    def merge_n_lists(self, lists):
        class HeapNode:
            def __init__(self, node):
                self.node = node

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

        min_heap = []

        for l in lists:
            if l:
                heapq.heappush(min_heap, HeapNode(l))

        dummy = ListNode(0)
        current = dummy

        while min_heap:
            smallest_node = heapq.heappop(min_heap).node
            current.next = smallest_node
            current = current.next
            if smallest_node.next:
                heapq.heappush(min_heap, HeapNode(smallest_node.next))

        return dummy.next

JavaScript

The JS solution uses divide and conquer instead of a heap, since JavaScript lacks a built-in priority queue.

class Solution {
  mergeNLists(lists) {
    if (!lists || lists.length === 0) return null;

    const mergeTwoLists = (l1, l2) => {
      const dummy = new ListNode(0);
      let current = dummy;

      while (l1 !== null && l2 !== null) {
        if (l1.data < l2.data) {
          current.next = l1;
          l1 = l1.next;
        } else {
          current.next = l2;
          l2 = l2.next;
        }
        current = current.next;
      }

      if (l1 !== null) current.next = l1;
      if (l2 !== null) current.next = l2;

      return dummy.next;
    };

    const mergeNListsHelper = (lists, start, end) => {
      if (start === end) return lists[start];
      const mid = Math.floor((start + end) / 2);
      const left = mergeNListsHelper(lists, start, mid);
      const right = mergeNListsHelper(lists, mid + 1, end);
      return mergeTwoLists(left, right);
    };

    return mergeNListsHelper(lists, 0, lists.length - 1);
  }
}

TypeScript

Same divide-and-conquer approach as JavaScript, with full type annotations.

class Solution {
  mergeNLists(lists: (ListNode | null)[]): ListNode | null {
    if (!lists || lists.length === 0) return null;

    const mergeTwoLists = (
      l1: ListNode | null,
      l2: ListNode | null
    ): ListNode | null => {
      const dummy = new ListNode(0);
      let current = dummy;

      while (l1 !== null && l2 !== null) {
        if (l1.data < l2.data) {
          current.next = l1;
          l1 = l1.next;
        } else {
          current.next = l2;
          l2 = l2.next;
        }
        current = current.next;
      }

      if (l1 !== null) current.next = l1;
      if (l2 !== null) current.next = l2;

      return dummy.next;
    };

    const mergeNListsHelper = (
      lists: (ListNode | null)[],
      start: number,
      end: number
    ): ListNode | null => {
      if (start === end) return lists[start];
      const mid = Math.floor((start + end) / 2);
      const left = mergeNListsHelper(lists, start, mid);
      const right = mergeNListsHelper(lists, mid + 1, end);
      return mergeTwoLists(left, right);
    };

    return mergeNListsHelper(lists, 0, lists.length - 1);
  }
}

C++

#include <vector>
#include <queue>

class Solution {
public:
  ListNode* mergeNLists(std::vector<ListNode*> &lists) {
    auto compare = [](ListNode* a, ListNode* b) {
      return a->data > b->data;
    };

    std::priority_queue<ListNode*, std::vector<ListNode*>,
                        decltype(compare)> minHeap(compare);

    for (auto list : lists) {
      if (list) {
        minHeap.push(list);
      }
    }

    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (!minHeap.empty()) {
      ListNode* minNode = minHeap.top();
      minHeap.pop();
      tail->next = minNode;
      tail = tail->next;

      if (minNode->next) {
        minHeap.push(minNode->next);
      }
    }

    return dummy.next;
  }
};

Go

Go uses an iterative divide-and-conquer approach, merging lists in pairs and doubling the interval each pass.

func MergeNLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    mergeTwoLists := func(l1, l2 *ListNode) *ListNode {
        dummy := &ListNode{}
        current := dummy

        for l1 != nil && l2 != nil {
            if l1.Data < l2.Data {
                current.Next = l1
                l1 = l1.Next
            } else {
                current.Next = l2
                l2 = l2.Next
            }
            current = current.Next
        }

        if l1 != nil {
            current.Next = l1
        } else {
            current.Next = l2
        }

        return dummy.Next
    }

    interval := 1
    for interval < len(lists) {
        for i := 0; i+interval < len(lists); i += interval * 2 {
            lists[i] = mergeTwoLists(lists[i], lists[i+interval])
        }
        interval *= 2
    }

    return lists[0]
}

Scala

import scala.collection.mutable.PriorityQueue

class Solution {
  def mergeNLists(lists: Array[ListNode]): ListNode = {
    implicit val listNodeOrdering: Ordering[ListNode] =
      Ordering.by(-_.data)

    val minHeap = PriorityQueue.empty[ListNode]

    lists.foreach { list =>
      if (list != null) minHeap.enqueue(list)
    }

    val dummyHead = ListNode(0)
    var current = dummyHead

    while (minHeap.nonEmpty) {
      val smallestNode = minHeap.dequeue()
      current.next = smallestNode
      current = current.next
      if (smallestNode.next != null) {
        minHeap.enqueue(smallestNode.next)
      }
    }

    dummyHead.next
  }
}

Kotlin

import java.util.PriorityQueue

class Solution {
    fun mergeNLists(lists: Array<ListNode>): ListNode? {
        if (lists.isEmpty()) {
            return null
        }

        val minHeap = PriorityQueue<ListNode>(compareBy { it.data })

        lists.forEach { node ->
            node?.let { minHeap.offer(it) }
        }

        val dummy = ListNode(0)
        var current = dummy

        while (minHeap.isNotEmpty()) {
            val minNode = minHeap.poll()
            current.next = minNode
            current = current.next!!

            minNode.next?.let { minHeap.offer(it) }
        }

        return dummy.next
    }
}

Swift

Swift lacks a built-in priority queue, so this solution includes a lightweight MinHeap struct.

class Solution {
    func mergeNLists(_ lists: [ListNode?]) -> ListNode? {
        if lists.isEmpty { return nil }

        var minHeap = MinHeap()

        for node in lists {
            if let node = node {
                minHeap.insert(node)
            }
        }

        let dummy = ListNode(0)
        var current = dummy

        while !minHeap.isEmpty {
            let minNode = minHeap.extractMin()!
            current.next = minNode
            current = current.next!

            if let nextNode = minNode.next {
                minHeap.insert(nextNode)
            }
        }

        return dummy.next
    }

    struct MinHeap {
        var heap: [ListNode] = []
        var isEmpty: Bool { heap.isEmpty }

        mutating func insert(_ node: ListNode) {
            heap.append(node)
            siftUp(heap.count - 1)
        }

        mutating func extractMin() -> ListNode? {
            guard !heap.isEmpty else { return nil }
            if heap.count == 1 { return heap.removeLast() }
            let min = heap[0]
            heap[0] = heap.removeLast()
            siftDown(0)
            return min
        }

        private mutating func siftUp(_ index: Int) {
            var child = index
            var parent = (child - 1) / 2
            while child > 0 && heap[child].data < heap[parent].data {
                heap.swapAt(child, parent)
                child = parent
                parent = (child - 1) / 2
            }
        }

        private mutating func siftDown(_ index: Int) {
            var parent = index
            while true {
                let left = 2 * parent + 1
                let right = 2 * parent + 2
                var smallest = parent
                if left < heap.count && heap[left].data < heap[smallest].data {
                    smallest = left
                }
                if right < heap.count && heap[right].data < heap[smallest].data {
                    smallest = right
                }
                if smallest == parent { break }
                heap.swapAt(parent, smallest)
                parent = smallest
            }
        }
    }
}

Rust

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

impl Solution {
    pub fn merge_n_lists(
        &self,
        lists: Vec<Option<Box<ListNode>>>
    ) -> Option<Box<ListNode>> {
        if lists.is_empty() { return None; }

        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
    }
}

C#

public class Solution {
    public ListNode? MergeNLists(ListNode?[] lists) {
        if (lists == null || lists.Length == 0) {
            return null;
        }

        var minHeap = new PriorityQueue<ListNode, int>();

        foreach (var node in lists) {
            if (node != null) minHeap.Enqueue(node, node.data);
        }

        var dummy = new ListNode(0);
        var current = dummy;

        while (minHeap.Count > 0) {
            var minNode = minHeap.Dequeue();
            current.next = minNode;
            current = current.next;

            if (minNode.next != null)
                minHeap.Enqueue(minNode.next, minNode.next.data);
        }

        return dummy.next;
    }
}

Dart

class Solution {
  ListNode? mergeNLists(List<ListNode?> lists) {
    if (lists.isEmpty) return null;

    List<ListNode> minHeap = [];
    for (ListNode? node in lists) {
      if (node != null) minHeap.add(node);
    }
    minHeap.sort((a, b) => a.data.compareTo(b.data));

    ListNode dummy = ListNode(0);
    ListNode current = dummy;

    while (minHeap.isNotEmpty) {
      ListNode minNode = minHeap.removeAt(0);
      current.next = minNode;
      current = current.next!;

      if (minNode.next != null) {
        _insertSorted(minHeap, minNode.next!);
      }
    }

    return dummy.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);
  }
}

PHP

class Solution {
    public function mergeNLists(array $lists): ?ListNode {
        if (empty($lists)) {
            return null;
        }

        $minHeap = new SplPriorityQueue();
        $counter = 0;

        foreach ($lists as $node) {
            if ($node !== null) {
                $minHeap->insert($node, [-$node->data, $counter++]);
            }
        }

        $dummy = new ListNode(0);
        $current = $dummy;

        while (!$minHeap->isEmpty()) {
            $minNode = $minHeap->extract();
            $current->next = $minNode;
            $current = $current->next;

            if ($minNode->next !== null) {
                $minHeap->insert(
                    $minNode->next,
                    [-$minNode->next->data, $counter++]
                );
            }
        }

        return $dummy->next;
    }
}

Ruby

Ruby uses divide and conquer with a recursive split-and-merge pattern.

class Solution
  def merge_n_lists(lists)
    return nil if lists.nil? || lists.empty?
    merge_lists_helper(lists, 0, lists.length - 1)
  end

  def merge_lists_helper(lists, left, right)
    return lists[left] if left == right
    mid = (left + right) / 2
    left_merged = merge_lists_helper(lists, left, mid)
    right_merged = merge_lists_helper(lists, mid + 1, right)
    merge_two_lists(left_merged, right_merged)
  end

  def merge_two_lists(l1, l2)
    dummy = ListNode.new(0)
    current = dummy

    while l1 && l2
      if l1.data < l2.data
        current.next = l1
        l1 = l1.next
      else
        current.next = l2
        l2 = l2.next
      end
      current = current.next
    end

    current.next = l1 || l2
    dummy.next
  end
end