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.length0 <= k <= 1040 <= lists[i].length <= 500-104 <= lists[i][j] <= 104lists[i] is sorted in ascending order.lists[i].length will not exceed 104.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.
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.
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.
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.
This approach follows the divide-and-conquer methodology to merge the lists incrementally.
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.
C++
JavaScript
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.
| Approach | Complexity |
|---|---|
| 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. |
| Divide and Conquer | Time Complexity: O(N log k), where N is the total number of nodes and k is the number of lists. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sequential Merge | O(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 Conquer | O(N log k) | O(log k) | Efficient when recursion or pairwise merging is preferred |
Merge K Sorted Lists - Leetcode 23 - Python • NeetCode • 292,867 views views
Watch 9 more video solutions →Practice Merge k Sorted Lists with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor