Skip to main content
Talentd

Merge k Sorted Lists - Solution & Explanation

HardLinked ListDivide and ConquerHeap (Priority Queue)Merge Sort17 min readAsked at: Amazon, Microsoft, Apple +47
Practice this problem

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.

Approach Overview

Problem Overview: You receive k sorted linked lists and must merge them into one sorted linked list. The final list must preserve sorted order while efficiently handling all nodes across the input lists.

Approach 1: Sequential Merge (O(Nk) time, O(1) space)

The simplest idea merges lists one at a time. Start with the first list, merge it with the second, then merge the result with the third, and continue until all lists are processed. Each merge operation works like the classic merge step in merge sort, comparing node values and appending the smaller one to the result. The problem is repeated work: nodes from earlier lists get compared again every time a new list is merged. With N total nodes and k lists, the overall cost grows to O(Nk). This approach is easy to implement but inefficient when k is large.

Approach 2: Merge Using a Min-Heap (O(N log k) time, O(k) space)

A more scalable solution keeps track of the smallest current node across all lists using a min-heap. Push the head of every list into a heap keyed by node value. Repeatedly extract the smallest node, append it to the result list, and insert the next node from the same list into the heap. The heap size never exceeds k, so each push or pop costs O(log k). Since every one of the N nodes is inserted and removed exactly once, the total complexity becomes O(N log k) with O(k) extra space. This approach heavily relies on the heap (priority queue) data structure to efficiently track the smallest candidate node.

Approach 3: Divide and Conquer (O(N log k) time, O(log k) space)

This method applies the same strategy used by divide and conquer algorithms. Pair up lists and merge them in parallel: first merge list 1 with list 2, list 3 with list 4, and so on. After one pass, the number of lists halves. Repeat the process until only one list remains. Each level processes all N nodes, and there are log k levels of merging, leading to O(N log k) time complexity. Space usage is O(log k) if implemented recursively due to the call stack. The benefit is that each node participates in far fewer comparisons than in the sequential merge approach.

Recommended for interviews: The min-heap solution is the most commonly expected answer because it demonstrates knowledge of priority queues and efficient multi-way merging. The divide and conquer approach is equally optimal and often preferred when interviewers want to test algorithmic reasoning around recursive merging. Showing the sequential merge idea first demonstrates baseline understanding, while moving to the O(N log k) strategies shows strong optimization skills.

Approach 1: Merge Using a Min-Heap

This approach utilizes a min-heap (priority queue) to efficiently merge k sorted linked lists. The heap will help us identify the minimum element among the lists efficiently.

  • Initial step involves inserting the head of each list into the min-heap.
  • Then, continuously extract the smallest element from the min-heap and append it to the merged list.
  • If there’s a next element in the list from which the node was extracted, push that into the min-heap.

This ensures that the smallest elements are appended to the resulting list in sorted order.

The Python solution uses the built-in heapq module which provides an efficient priority queue implementation. Each ListNode is wrapped so that it is comparable based on its val, allowing the heap operations to work correctly. The solution maintains a heap of size k, thus ensuring efficient merging.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(N log k), where N is the total number of nodes and k is the number of linked lists. Each insertion and extraction from the heap takes log k time, and there are N nodes in total.
Space Complexity: O(k), due to the heap that at most stores one node from each list.

Try this approach in the editor →

Approach 2: Divide and Conquer

This approach follows the divide-and-conquer methodology to merge the lists incrementally.

  • Recursively divide the array of lists into two halves until you have single lists to merge.
  • Then, merge the two halves by recursively calling and merging further down the line, akin to a merge sort process.

The C++ solution uses a divide-and-conquer strategy to break down the problem into smaller instances, which are solved recursively. The two halves of the list array are merged progressively, much like the merge step in merge sort.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(N log k), where N is the total number of nodes and k is the number of lists.
Space Complexity: O(log k) for recursion stack space.

Try this approach in the editor →

Approach 3: Priority Queue (Min Heap)

We can create a min heap pq to maintain the head nodes of all linked lists. Each time, we take out the node with the smallest value from the min heap, add it to the end of the result linked list, and then add the next node of this node to the heap. Repeat the above steps until the heap is empty.

The time complexity is O(n times log k), and the space complexity is O(k). Here, n is the total number of all linked list nodes, and k is the number of linked lists given in the problem.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHP

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Merge Using a Min-Heap

Time Complexity: O(N log k), where N is the total number of nodes and k is the number of linked lists. Each insertion and extraction from the heap takes log k time, and there are N nodes in total.
Space Complexity: O(k), due to the heap that at most stores one node from each list.

Divide and Conquer

Time Complexity: O(N log k), where N is the total number of nodes and k is the number of lists.
Space Complexity: O(log k) for recursion stack space.

Priority Queue (Min Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sequential MergeO(Nk)O(1)Simple baseline solution or when k is very small
Min-Heap (Priority Queue)O(N log k)O(k)Best general solution when merging many sorted lists
Divide and ConquerO(N log k)O(log k)Efficient when recursion or pairwise merging is preferred

Video Solution

Merge K Sorted Lists - Leetcode 23 - Python • NeetCode • 306,392 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Merge k Sorted Lists easy or hard?
Merge k Sorted Lists is classified as a hard problem because it combines linked list manipulation with advanced algorithm design. Efficient solutions require understanding heaps or divide and conquer techniques to achieve O(N log k) performance.
Merge k Sorted Lists Python/Java solution
Python typically uses the heapq module to implement the min-heap, while Java uses PriorityQueue. Both implementations push the head nodes of each list, repeatedly extract the smallest value, and append it to the result list.
How to solve Merge k Sorted Lists in O(N log k)?
Use either a priority queue or a divide and conquer strategy. The heap approach always extracts the smallest node among the current list heads in O(log k) time. Since every node is processed once, the total runtime becomes O(N log k).
What is the best approach for Merge k Sorted Lists?
The most practical approach uses a min-heap (priority queue). Insert the head node of each of the k lists into the heap, repeatedly extract the smallest node, and push its next node. This keeps the heap size at most k and processes all N nodes in O(N log k) time with O(k) extra space.
Is Merge k Sorted Lists asked at Google/Amazon/Meta?
Merge k Sorted Lists appears frequently in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests understanding of linked lists, heaps, and efficient multi-way merging techniques.
What data structure is used in Merge k Sorted Lists?
The most common data structure used is a min-heap (priority queue) to track the smallest node among the k lists. Linked list pointers are used to build the final merged list as nodes are extracted from the heap.
What is the time complexity of Merge k Sorted Lists?
The optimal solutions run in O(N log k) time where N is the total number of nodes across all lists and k is the number of lists. Both the min-heap approach and the divide and conquer merging strategy achieve this complexity.

Ready to solve this problem?

Practice Merge k Sorted Lists with our built-in code editor and test cases.

Practice on FleetCode
Previous

Merge Two Sorted Lists

Next

Smallest Subarrays With Maximum Bitwise OR