LeetCode · #23

Merge k Sorted Lists Solution

Merge k sorted linked lists into one sorted linked list and return its head.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #23

🏗️

Pattern

Min-Heap or Divide & Conquer

You are given an array of k linked lists lists, each sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

Example

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

Constraints

 • k == lists.length • 0 ≤ k ≤ 10⁴ • 0 ≤ lists[i].length ≤ 500 • -10⁴ ≤ lists[i][j] ≤ 10⁴ • Total nodes ≤ 10⁴ 

Section Two · Approach 1

Merge One-by-One — O(n · k)

Merge list 1 into list 2, then result into list 3, etc. Each merge is O(n), and we do k-1 merges. The merged list grows, making later merges expensive: total O(n·k).

Problem: The merged list keeps growing, so each subsequent merge gets longer. Using a min-heap or divide-and-conquer ensures we always pick the smallest element efficiently, reducing to O(n log k).

Section Three · Approach 2

Min-Heap / Divide & Conquer — O(n log k)

Min-Heap: Maintain a heap of size k holding the current head of each list. Pop the smallest, link it to the result, push the next node from that list. Each pop/push is O(log k), and we process n total nodes.

Divide & Conquer: Pair up lists and merge each pair. Repeat until one list remains — like merge sort's merge phase. log k rounds, each processing n total nodes.

💡 Mental model (Heap): Imagine k conveyor belts, each delivering items in order. A judge stands at the merge point with a "smallest item display" (the heap). They always pick from the belt with the smallest current item and place it on the output belt. Checking k belts with a heap takes O(log k) per pick.

Algorithm — Min-Heap

Step 1: Add the head of each non-null list to a min-heap (ordered by node value).
Step 2: While heap is not empty: pop smallest node, link to result.
Step 3: If popped node has a next, push next to heap.
Step 4: Return dummy.next.

🎯 Divide & Conquer alternative:

Merge lists[0] with lists[k/2], lists[1] with lists[k/2+1], etc. Reduces k lists to k/2. Repeat log k times.
Same O(n log k) complexity, no heap needed — useful in languages without a built-in priority queue.

Section Four · Trace

Visual Walkthrough

Trace min-heap approach with [[1,4,5],[1,3,4],[2,6]]:

Min-Heap — always extract the smallest head

Section Five · Implementation

Code — Java & Python

Java — Min-Heap (PriorityQueue)

 import java.util.PriorityQueue;
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>(
            (a, b) -> a.val - b.val);
for (ListNode head : lists)
if (head != null) heap.offer(head);
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!heap.isEmpty()) {
ListNode node = heap.poll();
            tail.next = node;
            tail = tail.next;
if (node.next != null)
                heap.offer(node.next);
        }
return dummy.next;
    }
}

Python — Min-Heap (heapq)

 import heapq
class Solution:
def mergeKLists(self, lists: list) -> Optional[ListNode]:
        heap = []
for i, head in enumerate(lists):
if head:
                heapq.heappush(heap, (head.val, i, head))

        dummy = tail = ListNode(0)
while heap:
            val, i, node = heapq.heappop(heap)
            tail.next = node
            tail = tail.next
if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Merge one-by-one	O(n · k)	O(1)	Simple but slow for large k
Collect + sort	O(n log n)	O(n)	Ignores sorted structure
Min-Heap ← optimal	O(n log k)	O(k)	Heap of size k, pop/push log k each
Divide & Conquer	O(n log k)	O(log k)	Recursion stack for pairing

n = total nodes across all lists.:

The heap holds at most k nodes (one per list).
Each of the n nodes is pushed and popped once — O(log k) per operation → O(n log k) total.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty array	`[]`	No lists → return null. Heap starts empty.
All empty lists	`[null, null]`	Nothing added to heap → return null.
Single list	`[[1,2,3]]`	Return it as-is — no merge needed.
k=10⁴, short lists	Many single-node lists	Heap of 10⁴ — still fast (log 10⁴ ≈ 14).

⚠ Common Mistake (Python): Pushing (node.val, node) to heapq. When two nodes have the same value, Python tries to compare nodes (which aren't comparable). Include a tiebreaker index: (node.val, i, node) where i is a unique counter.

← Back to Linked List problems

LearningTree

LC 23 · Merge k Sorted Lists — Solution & Explanation | DSA Guide