Start learning free

LESSON 440 OF 671 · LINKED LISTS

Merge K Sorted Lists

Practice O(n × k)

You get lists, an array of k sorted linked lists.

Merge them all into one sorted list, and return its head.

 

Example 1:

Input: lists = [[2,5,9],[1,5],[3,4,10]]
Output: [1,2,3,4,5,5,9,10]
Explanation: The three lists are:
  2 -> 5 -> 9
  1 -> 5
  3 -> 4 -> 10
The answer has all eight values in order.
Both 5s stay.

Example 2:

Input: lists = [[-6,-1],[],[-6]]
Output: [-6,-6,-1]
Explanation: The empty list adds nothing.
Both -6s stay, one from each list.

Example 3:

Input: lists = [[],[]]
Output: []
Explanation: Both lists are empty.
So the answer is nil.

 

Constraints:

  • 0 to 10,000 lists (lists itself can be empty).
  • Each list has 0 to 500 nodes.
  • All lists together have at most 10,000 nodes.
  • Each value is from -10,000 to 10,000,000.
  • Every list is in ascending order.
Note:

Your algorithm should run in O(n × k) time and use O(1) extra space apart from the merged list's new nodes (one per value), where n is the total number of nodes across all lists and k is the number of lists.
(A faster O(n log k) solution, with a min-heap, has its own lesson.)


Hints:

The output is sorted: at every moment you only need the smallest current head across all lists.
What's the simplest way to find it?

Use a dummy sentinel node and a tail walker.
Each iteration: scan all k heads, pick the smallest, append a new node with its value after tail, move tail onto it, and advance the chosen list. Repeat until every list is exhausted.

We produce n output nodes, and each one costs an O(k) scan of all heads — Time Complexity is O(n × k).
Apart from the merged list it returns (one new node per value), the solution keeps only the dummy node and a few variables, so the Extra Space is O(1).
STEP 1 OF 11
    Ctrl + Enter to check