Skip to content

Volume ITechnology

4.9.10 — Merge K Sorted Lists ​

LeetCode 23 · Hard · ★ Blind 75

The problem ​

You are given a list called lists that holds k linked lists. Each linked list is already sorted from smallest to largest. Merge them all into one sorted linked list and return its head.

lists = [1 → 4 → 5,  1 → 3 → 4,  2 → 6]
result: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

lists = []      →  (empty)
lists = [ [] ]  →  (empty)

There can be up to 10,000 lists, with up to 10,000 nodes in total. We will call the total number of nodes N.

What the problem is really asking ​

You already know how to merge two sorted lists from 4.9.2: look at both front nodes and take the smaller one.

With k lists, the next node of the answer is still one of the front nodes, the smallest of k of them. So the real question is: how do you find the smallest of k front nodes quickly, over and over? Or, put another way: in what order should you merge the lists, so you do not redo work?

The brute force, and where it wastes work ​

Merge the lists one at a time. Merge list 1 with list 2. Merge that result with list 3. Then with list 4, and so on.

python
def mergeKLists(lists):
    result = None
    for lst in lists:
        result = mergeTwo(result, lst)    # the 4.9.2 merge
    return result

Each merge walks the whole result built so far. That result grows every time. By the end, the early nodes have been walked about k times each. The total is O(N \cdot k). With 10,000 lists, that is 10,000 walks over a growing list.

The waste in one sentence: the nodes merged early get walked again in every later merge.

Solution 1 — merge in pairs ​

Merge list 1 with list 2, list 3 with list 4, list 5 with list 6, and so on. That halves the number of lists in one round. Repeat until one list is left.

Why is this better? Each round halves the number of lists, so there are only about \log_2 k rounds. Read \log_2 k as "log base 2 of k", which is how many times you can halve k before reaching 1. For 10,000 lists that is about 14. In each round, every node is walked once. So each node is walked about 14 times, not 10,000 times.

This version needs no extra data structure, so it works well in TypeScript, which has no built-in heap.

python
class Solution:
    def mergeKLists(self, lists):
        if not lists:                                        # (1)
            return None

        while len(lists) > 1:                                # (2)
            merged = []
            for i in range(0, len(lists), 2):                # (3)
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None   # (4)
                merged.append(self.mergeTwo(l1, l2))
            lists = merged                                   # (5)

        return lists[0]                                      # (6)

    def mergeTwo(self, l1, l2):                              # (7)
        dummy = tail = ListNode()
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next
ts
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (lists.length === 0) return null;                       // (1)

  while (lists.length > 1) {                                 // (2)
    const merged: Array<ListNode | null> = [];
    for (let i = 0; i < lists.length; i += 2) {              // (3)
      const l1 = lists[i];
      const l2 = i + 1 < lists.length ? lists[i + 1] : null; // (4)
      merged.push(mergeTwo(l1, l2));
    }
    lists = merged;                                          // (5)
  }

  return lists[0];                                           // (6)
}

function mergeTwo(l1: ListNode | null, l2: ListNode | null): ListNode | null {  // (7)
  const dummy = new ListNode();
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 ?? l2;
  return dummy.next;
}

Line by line ​

(1) No lists at all means an empty result.

(2) Keep halving until only one list is left.

(3) Step through the lists two at a time. range(0, len(lists), 2) gives 0, 2, 4, and so on, so i and i + 1 form a pair.

(4) A list with no partner. If there is an odd number of lists, the last one has no pair. We merge it with None, which simply returns it unchanged, so it moves on to the next round.

(5) The merged lists become the lists for the next round. There are now about half as many.

(6) The one list left is the answer.

(7) The two-list merge from 4.9.2, unchanged. A dummy head, take the smaller front node each time, and attach the leftovers at the end.

Trace ​

Take the three lists A = 1 → 4 → 5, B = 1 → 3 → 4, C = 2 → 6.

RoundLists beforePairs mergedLists after
1A, B, CA with B → 1 → 1 → 3 → 4 → 4 → 5; C with nothing → 2 → 62 lists
2the two abovemerged → 1 → 1 → 2 → 3 → 4 → 4 → 5 → 61 list

Two rounds, and the result is correct.

Solution 2 — a heap of the k front nodes ​

The next node of the answer is always the smallest of the k front nodes. A min-heap is a structure that always hands you its smallest item, and adding or removing an item costs only O(\log m) for a heap of m items. 4.16 explains how it works inside.

Put the front node of each list into the heap. Then repeat: take the smallest node out, attach it to the answer, and put the next node from that same list into the heap in its place.

Think of k queues of people, each queue already ordered by height. To build one combined queue by height, you only ever need to look at the person at the front of each queue. Take the shortest of those, and the next person in that queue steps up to the front. The heap is a helper that tells you the shortest front person instantly, without you checking every queue.

python
import heapq

class Solution:
    def mergeKLists(self, lists):
        heap = []                                            # (1)
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))    # (2)

        dummy = tail = ListNode()                            # (3)
        while heap:                                          # (4)
            val, i, node = heapq.heappop(heap)               # (5)
            tail.next = node
            tail = node
            if node.next:                                    # (6)
                heapq.heappush(heap, (node.next.val, i, node.next))

        return dummy.next

(1) The heap starts empty.

(2) Add each list's front node, skipping empty lists. We push a group of three things: (value, i, node). Python's heap orders these groups by their first item, the value.

The i in the middle is there for a real reason. When two nodes have equal values, Python compares the next item to break the tie. If the next item were the node, Python would try to compare two ListNode objects, which it does not know how to do, and it would crash with a TypeError. The list number i is a plain number, so ties are broken there and the nodes are never compared. Almost everyone hits this bug once.

(3) A dummy head and a tail, as in every list-building problem.

(4) Keep going while any front nodes remain.

(5) Take the smallest front node and attach it to the answer.

(6) Its list's next node becomes that list's new front, so push it in. The heap never holds more than k items, one per list.

Complexity, derived ​

One at a time. About k merges, each walking up to N nodes. O(N \cdot k).

Pairs. About \log k rounds. In each round, every node is walked once, which is O(N). So the total is O(N \log k). The only extra memory is the list of heads, so O(1) beyond that if you reuse the input list.

Heap. Each of the N nodes is pushed once and popped once. The heap never holds more than k items, so each push or pop is O(\log k). The total is O(N \log k). The heap uses O(k) memory.

ApproachTimeExtra memory
one at a timeO(N \cdot k)O(1)
merge in pairsO(N \log k)O(1)
heap of frontsO(N \log k)O(k)

Which one to write ​

Both fast versions have the same time. The heap version suits data that arrives as it is produced, because it only needs the current front of each list. Merging in pairs suits the case where all lists are available up front, and it needs no heap. Say both, pick one, and say why.

Edge cases ​

  • No lists, []. Return None.
  • Only empty lists, [None, None]. Pairs: merging two empties gives an empty list. Heap: nothing is pushed, and the answer is empty.
  • One list. It is already the answer.
  • Equal values across lists. The heap version needs the i tie-breaker. The pairs version handles them with <=.

Variations you will meet ​

The k-way merge is a real operation in large systems, not just an exercise.

  • Sorting a file too big for memory. Split it into chunks small enough to sort in memory, sort each chunk, then merge all the sorted chunks with a heap of their front lines. This is how databases sort huge tables.
  • Kth Smallest Element in a Sorted Matrix. Each row is a sorted list. Keep a heap of each row's front.
  • Smallest Range Covering Elements from K Lists. The same heap of fronts, while also tracking the largest front.

The general lesson: when you need the smallest item across k sorted sources, keep one candidate from each source in a heap.

What the interviewer will push on ​

"Why is merging one at a time O(N \cdot k)?" The growing result is walked again in every merge.

"Why does merging in pairs fix it?" Halving gives about \log k rounds, and each round walks every node once.

"Why do you push a three-part group with an index into the heap?" To break ties between equal values without ever comparing two nodes.

"How big does the heap get?" At most k, because each pop is followed by at most one push from the same list.

One thing to volunteer: give the cost of all three approaches in one breath, then choose one. That comparison is the real answer to this problem. The merging itself you already knew.

Next: 4.9.11 Reverse Nodes in k-Group. The hardest pointer bookkeeping in the chapter.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet