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 need to merge them into a single sorted linked list. Each list is already sorted in ascending order, so the challenge is efficiently choosing the smallest current node among the k lists until all nodes are merged.
Approach 1: Merge Using a Min-Heap (Priority Queue) (Time: O(N log k), Space: O(k))
Push the head node of each list into a min-heap. The heap always exposes the smallest node across the k lists. Pop the smallest node, append it to the merged result, and push its next node into the heap if it exists. Each insertion or removal from the heap costs O(log k), and every node is processed exactly once, leading to total time O(N log k) where N is the total number of nodes across all lists. The heap stores at most k nodes at a time, giving O(k) extra space. This approach directly models the “pick the smallest among k options” requirement and relies on a Heap (Priority Queue) to maintain ordering.
Approach 2: Divide and Conquer (Time: O(N log k), Space: O(log k))
Treat the problem like the merge phase of Merge Sort. Instead of merging all lists at once, repeatedly merge them in pairs. First merge list pairs (0 with 1, 2 with 3, etc.), producing k/2 lists. Continue this process until only one list remains. Each merge operation between two sorted linked lists runs in O(n) time for their combined size. Since the number of lists halves each round, the total work across all levels becomes O(N log k). The recursion depth contributes O(log k) auxiliary space. This approach uses classic techniques from Divide and Conquer and works well when you want predictable memory usage without a heap.
Recommended for interviews: The min-heap approach is usually the first solution interviewers expect because it directly handles the "k-way merge" pattern and clearly demonstrates understanding of priority queues. Divide and conquer is equally optimal in time complexity and shows deeper algorithmic thinking by adapting the merge two sorted lists pattern repeatedly. Showing both approaches signals strong command of Linked List manipulation and scalable merging strategies.
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.
Java
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.
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 |
|---|---|---|---|
| Min-Heap (Priority Queue) | O(N log k) | O(k) | Best when handling many sorted lists simultaneously and you want the smallest element efficiently at each step |
| Divide and Conquer | O(N log k) | O(log k) | Useful when applying merge-sort style recursion or avoiding an explicit heap data structure |
Merge K Sorted Lists - Leetcode 23 - Python • NeetCode • 236,566 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