Merge k Sorted Lists
Module 19 · Heaps
Problem
You are given an array of k linked lists, each already sorted in
ascending order. Merge them into one sorted linked list and return its
head.
Examples
Example 1
lists = [[1,4,5],[1,3,4],[2,6]]Output[1,1,2,3,4,4,5,6]Example 2
lists = []Output[]Example 3
lists = [[]]Output[]Constraints
k up to 10⁴, total nodes n up to ~10⁴, node values in ±10⁴. Lists may be empty.
Attempt it first
You already know how to merge two sorted lists in O(total) time — the two-pointer merge from the Sorting module (it's the core of merge sort). The whole problem is: how do you extend that to k lists without wasting work? Before reading on, think about what the merge step actually needs at each moment. To pick the next node of the output, you compare the current heads of the lists and take the smallest. With k lists, you have k heads to compare each time — what structure turns "find the smallest of k things, repeatedly, as they change" into something cheap?