# Merge k Sorted Lists **Difficulty:** HARD [External](https://leetcode.com/problems/merge-k-sorted-lists) Canonical: https://scaleengineer.com/dsa/problems/merge-k-sorted-lists **Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Merge Sort](https://scaleengineer.com/algorithms/merge-sort) **Data structures:** Linked List, Heap (Priority Queue) **Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Airbnb](https://scaleengineer.com/companies/airbnb), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [Deloitte](https://scaleengineer.com/companies/deloitte), [Docusign](https://scaleengineer.com/companies/docusign), [DoorDash](https://scaleengineer.com/companies/doordash), [Hubspot](https://scaleengineer.com/companies/hubspot), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Samsung](https://scaleengineer.com/companies/samsung), [Snowflake](https://scaleengineer.com/companies/snowflake), [SoFi](https://scaleengineer.com/companies/sofi), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [eBay](https://scaleengineer.com/companies/ebay), [Dell](https://scaleengineer.com/companies/dell), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [X](https://scaleengineer.com/companies/x), [Warnermedia](https://scaleengineer.com/companies/warnermedia), [Anduril](https://scaleengineer.com/companies/anduril), [IXL](https://scaleengineer.com/companies/ixl), [Indeed](https://scaleengineer.com/companies/indeed), [MongoDB](https://scaleengineer.com/companies/mongodb), [NetApp](https://scaleengineer.com/companies/netapp), [Nykaa](https://scaleengineer.com/companies/nykaa), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Rivian](https://scaleengineer.com/companies/rivian), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [Verkada](https://scaleengineer.com/companies/verkada) --- ## Problem 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`. # Approaches ## Merge Lists One by One This approach involves iteratively merging two lists at a time. We start with an empty list or the first list in the array, and then sequentially merge it with every other list in the input array until all lists are combined. This leverages the solution for the "Merge Two Sorted Lists" problem. **Time:** O(k * N) · **Space:** O(1) **Pros:** Low space complexity.; Relatively easy to implement if you already have a function to merge two sorted lists. **Cons:** Inefficient time complexity, especially when `k` is large. It repeatedly traverses the growing merged list. ### Explanation We initialize our result list, let's call it `mergedList`, with the first list from the input array (`lists[0]`). Then, we loop through the rest of the lists in the array, from the second list (`lists[1]`) to the last one. In each iteration, we merge the current `mergedList` with the current list from the array (`lists[i]`) using a helper function that merges two sorted linked lists. The result of this merge operation becomes the new `mergedList`. After iterating through all the lists, `mergedList` will contain all the nodes from all the input lists, sorted in ascending order. The helper function `mergeTwoLists` works by creating a dummy head for the new list and using two pointers to traverse the two input lists, always picking the smaller node to append to the new list. ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } ListNode mergedList = lists[0]; for (int i = 1; i < lists.length; i++) { mergedList = mergeTwoLists(mergedList, lists[i]); } return mergedList; } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode current = dummyHead; while (l1 != null && l2 != null) { if (l1.val < l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } if (l1 != null) { current.next = l1; } else { current.next = l2; } return dummyHead.next; } } ``` ### Algorithm - Handle the edge case where the input array `lists` is empty or null. - Initialize a `ListNode` called `mergedList` to `lists[0]`. - Iterate through the `lists` array from the second element (`i = 1`) to the end. - In each iteration, call a helper function `mergeTwoLists` to merge the current `mergedList` with `lists[i]`. - Update `mergedList` with the result of the merge. - Return `mergedList` after the loop finishes. ## Collect All Nodes and Sort This is a straightforward brute-force approach. The idea is to ignore the fact that the lists are already sorted, collect all the nodes from all `k` lists into a single data structure like an array or list, sort this collection, and then build a new sorted linked list from the sorted values. **Time:** O(N log N) · **Space:** O(N) **Pros:** Very simple to conceptualize and implement. **Cons:** High space complexity, as it requires storing all node values.; It doesn't take advantage of the fact that the input lists are already sorted, which leads to a non-optimal time complexity. ### Explanation First, we create a dynamic array (like `ArrayList` in Java) to hold the values of all nodes. We then iterate through each of the `k` linked lists. For each list, we traverse it from the head to the tail. During the traversal, we extract the value of each node and add it to our dynamic array. Once we have visited every node in every list, our array contains all the node values, but in no particular order. We then use a standard sorting algorithm (like `Collections.sort()` in Java) to sort this array of values in ascending order. Finally, we create a new linked list. We iterate through our sorted array of values, and for each value, we create a new `ListNode` and append it to the end of our new linked list. We use a dummy head node to simplify the process of building the new list. ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ import java.util.ArrayList; import java.util.Collections; import java.util.List; class Solution { public ListNode mergeKLists(ListNode[] lists) { List allValues = new ArrayList<>(); for (ListNode head : lists) { ListNode current = head; while (current != null) { allValues.add(current.val); current = current.next; } } Collections.sort(allValues); ListNode dummyHead = new ListNode(0); ListNode current = dummyHead; for (int val : allValues) { current.next = new ListNode(val); current = current.next; } return dummyHead.next; } } ``` ### Algorithm - Create a list, e.g., `ArrayList`, to store node values. - Iterate through the input array `lists`. - For each linked list, traverse it and add each node's value to the list of values. - Sort the list of values. - Create a new dummy `ListNode` to serve as the starting point of the merged list. - Iterate through the sorted values. For each value, create a new `ListNode` and append it to the merged list. - Return the `next` node of the dummy head. ## Merge with a Min-Heap A more optimized approach uses a Min-Heap (or a Priority Queue) to efficiently find the smallest node among the heads of all `k` lists. By always knowing the smallest current node, we can build the final sorted list step by step. **Time:** O(N log k) · **Space:** O(k) **Pros:** Optimal time complexity. It's significantly faster than the previous approaches for large `k`.; The logic is clean and directly addresses the problem of finding the minimum element at each step. **Cons:** Requires O(k) extra space for the heap, which can be significant if `k` is very large. ### Explanation The core idea is to maintain a Min-Heap of size at most `k`, containing the head node of each of the `k` lists. The heap is ordered by the node's value. We initialize the process by creating a `PriorityQueue` and adding the head node of each non-empty list to it. We also create a dummy head for our result list to simplify appending nodes. Then, we enter a loop that continues as long as the heap is not empty. In each iteration, we extract the minimum node from the heap (which is the smallest among all current heads). This is our next node in the sorted list. We append this node to our result list. If the extracted node has a `next` node in its original list, we add that `next` node to the heap. This ensures that we always consider the next available element from each list. This process is repeated until the heap is empty, at which point we have processed all nodes and built the complete sorted list. ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ import java.util.PriorityQueue; class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } // Min-heap to store the head of the lists PriorityQueue minHeap = new PriorityQueue<>((a, b) -> a.val - b.val); // Add the head of each list to the min-heap for (ListNode head : lists) { if (head != null) { minHeap.add(head); } } ListNode dummyHead = new ListNode(0); ListNode current = dummyHead; // Process nodes from the heap while (!minHeap.isEmpty()) { // Get the node with the smallest value ListNode smallestNode = minHeap.poll(); // Add it to the merged list current.next = smallestNode; current = current.next; // If there is a next node in the list, add it to the heap if (smallestNode.next != null) { minHeap.add(smallestNode.next); } } return dummyHead.next; } } ``` ### Algorithm - Create a `PriorityQueue` (Min-Heap) that compares `ListNode` objects by their `val`. - Iterate through the input `lists` array and add the head of each non-empty list to the heap. - Create a `dummyHead` node and a `current` pointer for the result list. - While the heap is not empty: a. Remove the smallest node from the heap using `poll()`. b. Append this node to the result list (`current.next`). c. Move `current` to this new node. d. If the removed node has a `next` element, add it to the heap. - Return `dummyHead.next`. ## Merge using Divide and Conquer This approach is analogous to the Merge Sort algorithm. It recursively divides the array of `k` lists into two halves, merges each half, and then merges the two resulting sorted lists. This pairing and merging process continues until only one list remains. **Time:** O(N log k) · **Space:** O(log k) **Pros:** Optimal time complexity, same as the Min-Heap approach.; Excellent space complexity, better than the Min-Heap approach. **Cons:** The recursive implementation might be slightly less intuitive than the Min-Heap approach for some. ### Explanation The strategy is to not merge lists one by one, but to merge them in pairs. We can implement this iteratively. We start by merging `lists[0]` with `lists[1]`, `lists[2]` with `lists[3]`, and so on. After this first pass, we have `k/2` lists. We repeat the process. In the next pass, we merge the new `lists[0]` with the new `lists[2]`, and so on. The number of lists to merge is halved in each pass. We continue this until only one list remains, which is the final sorted list. A more elegant way to implement this is recursively. A function `merge(lists, start, end)` would merge lists from index `start` to `end`. - The base case is when `start == end`, we just return `lists[start]`. - Otherwise, we find the middle `mid`, recursively call `merge(lists, start, mid)` and `merge(lists, mid + 1, end)`. - Finally, we merge the two sorted lists returned by the recursive calls. ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return merge(lists, 0, lists.length - 1); } private ListNode merge(ListNode[] lists, int start, int end) { if (start == end) { return lists[start]; } if (start > end) { return null; } int mid = start + (end - start) / 2; ListNode l1 = merge(lists, start, mid); ListNode l2 = merge(lists, mid + 1, end); return mergeTwoLists(l1, l2); } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode current = dummyHead; while (l1 != null && l2 != null) { if (l1.val < l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } if (l1 != null) { current.next = l1; } else { current.next = l2; } return dummyHead.next; } } ``` ### Algorithm - Define a recursive function `merge(lists, start, end)` that merges lists from index `start` to `end`. - The main function calls `merge(lists, 0, lists.length - 1)`. - **Base Case:** In `merge`, if `start > end`, return `null`. If `start == end`, return `lists[start]`. - **Recursive Step:** a. Calculate the middle index `mid`. b. Recursively call `merge` for the left half: `l1 = merge(lists, start, mid)`. c. Recursively call `merge` for the right half: `l2 = merge(lists, mid + 1, end)`. d. Merge the two resulting lists `l1` and `l2` using the standard `mergeTwoLists` helper function. e. Return the merged list. # Solutions ### CSharp ```csharp /** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode MergeKLists ( ListNode [] lists ) { int n = lists . Length ; if ( n == 0 ) { return null ; } for ( int i = 1 ; i < n ; ++ i ) { lists [ i ] = MergeTwoLists ( lists [ i - 1 ], lists [ i ]); } return lists [ n - 1 ]; } private ListNode MergeTwoLists ( ListNode l1 , ListNode l2 ) { ListNode dummy = new ListNode (); ListNode cur = dummy ; while ( l1 != null && l2 != null ) { if ( l1 . val <= l2 . val ) { cur . next = l1 ; l1 = l1 . next ; } else { cur . next = l2 ; l2 = l2 . next ; } cur = cur . next ; } cur . next = l1 == null ? l2 : l1 ; return dummy . next ; } } ``` ### Java ```java public class Merge_k_Sorted_Lists { public static void main ( String [] args ) { Merge_k_Sorted_Lists out = new Merge_k_Sorted_Lists (); Solution s = out . new Solution (); ListNode l1 = null ; ListNode l2 = new ListNode ( 1 ); s . mergeKLists ( new ListNode []{ l1 , l2 }); } public class Solution { public ListNode mergeKLists ( ListNode [] lists ) { if ( lists == null || lists . length == 0 ) { return null ; } // same as merge sort array return merge ( lists , 0 , lists . length - 1 ); } public ListNode merge ( ListNode [] lists , int start , int end ) { // single list if ( start == end ) { return lists [ start ]; } int mid = ( end - start ) / 2 + start ; ListNode leftHalf = merge ( lists , start , mid ); ListNode rightHalf = merge ( lists , mid + 1 , end ); return mergeTwoLists ( leftHalf , rightHalf ); } // from previous question: 21 Merge Two Sorted Lists public ListNode mergeTwoLists ( ListNode l1 , ListNode l2 ) { ListNode dummy = new ListNode ( 0 ); ListNode current = dummy ; while ( l1 != null || l2 != null ) { int v1 = ( l1 == null ? Integer . MAX_VALUE : l1 . val ); int v2 = ( l2 == null ? Integer . MAX_VALUE : l2 . val ); if ( v1 < v2 ) { current . next = l1 ; l1 = l1 . next ; } else { current . next = l2 ; l2 = l2 . next ; } current = current . next ; // now current is the new end node, but still pointing to next node current . next = null ; // @note: key, cut this node from l1 or l2 } return dummy . next ; } } } ////// class Solution_Heap { public ListNode mergeKLists ( ListNode [] lists ) { if ( lists == null || lists . length == 0 ) { return null ; } ListNode dummy = new ListNode ( 0 ); ListNode current = dummy ; // put 1st of each list to heap PriorityQueue < ListNode > heap = new PriorityQueue <>( ( a , b ) -> a . val - b . val ); // Arrays . stream ( lists ). filter ( Objects: : nonNull ). forEach ( heap: : offer ); while ( heap . size () != 0 ) { ListNode polled = heap . poll (); current . next = polled ; current = current . next ; if ( polled . next != null ) { heap . offer ( polled . next ); // @note: heap.offer()参数不能是null } } return dummy . next ; } } ////// /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists ( ListNode [] lists ) { int n = lists . length ; if ( n == 0 ) { return null ; } for ( int i = 0 ; i < n - 1 ; ++ i ) { lists [ i + 1 ] = mergeLists ( lists [ i ], lists [ i + 1 ]); } return lists [ n - 1 ]; } private ListNode mergeLists ( ListNode l1 , ListNode l2 ) { ListNode dummy = new ListNode (); ListNode cur = dummy ; while ( l1 != null && l2 != null ) { if ( l1 . val <= l2 . val ) { cur . next = l1 ; l1 = l1 . next ; } else { cur . next = l2 ; l2 = l2 . next ; } cur = cur . next ; } cur . next = l1 == null ? l2 : l1 ; return dummy . next ; } } ``` ### JavaScript ```javascript /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function (lists) { const n = lists.length; if (n == 0) { return null; } for (let i = 1; i < n; ++i) { lists[i] = mergeTwoLists(lists[i - 1], lists[i]); } return lists[n - 1]; }; function mergeTwoLists(l1, l2) { const dummy = new ListNode(); let cur = dummy; while (l1 && l2) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 || l2; return dummy.next; } ``` ### Python ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def mergeKLists ( self , lists : List [ Optional [ ListNode ]]) -> Optional [ ListNode ]: setattr ( ListNode , "__lt__" , lambda a , b : a . val < b . val ) pq = [ head for head in lists if head ] heapify ( pq ) dummy = cur = ListNode () while pq : node = heappop ( pq ) if node . next : heappush ( pq , node . next ) cur . next = node cur = cur . next return dummy . next # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next ###### import heapq ''' __lt__(self, other) for < __le__(self,other) for <= __gt__(self, other) for > __ge__(self, other) for >= ''' ''' # or create a wrapper class, without modifying existing node class class NodeWrapper: def __init__(self, node): self.node = node def __lt__(self, other): return self.node.val < other.node.val ''' # overwrite the comparison function, so the node can be comparable # or else, error, TypeError: '<' not supported between instances of 'ListNode' and 'ListNode' # define 'gt' will also work, so either lt or gt will do the compare job for ListNode # ListNode.__gt__ = lambda x, y: (x.val > y.val) ListNode . __lt__ = lambda x , y : ( x . val < y . val ) class Solution : def mergeKLists ( self , lists : List [ Optional [ ListNode ]]) -> Optional [ ListNode ]: dummy = current = ListNode () heap = [] for i , node in enumerate ( lists ): if node : # need to override # or else error: TypeError: '<' not supported between instances of 'ListNode' and 'ListNode' heapq . heappush ( heap , node ) while heap : anode = heapq . heappop ( heap ) current . next = anode current = current . next if anode . next : heapq . heappush ( heap , anode . next ) return dummy . next ''' tried to use node.val to order heap, but still got error TypeError: '<' not supported between instances of 'ListNode' and 'ListNode': heapq.heappush(heap, (node.val, node)) ''' ###### # based on merge 2 lists # note for empty input class Solution : def mergeKLists ( self , lists : List [ Optional [ ListNode ]]) -> Optional [ ListNode ]: if lists is None or len ( lists ) == 0 : return None return self . mergeKListsHelper ( lists , 0 , len ( lists ) - 1 ) def mergeKListsHelper ( self , lists : List [ Optional [ ListNode ]], start : int , end : int ) -> Optional [ ListNode ]: if start == end : return lists [ start ] mid = int (( start + end ) / 2 ) left = self . mergeKListsHelper ( lists , start , mid ) # print(left) right = self . mergeKListsHelper ( lists , mid + 1 , end ) # print(right) return self . mergeTwoLists ( left , right ) def mergeTwoLists ( self , list1 : Optional [ ListNode ], list2 : Optional [ ListNode ]) -> Optional [ ListNode ]: dummy = ListNode () current = dummy # print("merging: ", list1) # print("merging: ", list2) while list1 or list2 : v1 = list1 . val if list1 else float ( 'inf' ) v2 = list2 . val if list2 else float ( 'inf' ) if v1 < v2 : current . next = list1 list1 = list1 . next else : current . next = list2 list2 = list2 . next current = current . next # print("merging result: ", dummy.next) return dummy . next ############ # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def mergeKLists ( self , lists : List [ ListNode ]) -> ListNode : n = len ( lists ) if n == 0 : return None for i in range ( n - 1 ): # this is o(N) times of merge, while if use divide-mid-mere then it's o(logN) times of merge lists [ i + 1 ] = self . mergeTwoLists ( lists [ i ], lists [ i + 1 ]) return lists [ - 1 ] def mergeTwoLists ( self , l1 : ListNode , l2 : ListNode ) -> ListNode : dummy = ListNode () cur = dummy while l1 and l2 : if l1 . val <= l2 . val : cur . next = l1 l1 = l1 . next else : cur . next = l2 l2 = l2 . next cur = cur . next cur . next = l1 or l2 return dummy . next if __name__ == '__main__' : l1 = ListNode ( 1 ) l1 . next = ListNode ( 4 ) l1 . next . next = ListNode ( 5 ) l2 = ListNode ( 1 ) l2 . next = ListNode ( 3 ) l2 . next . next = ListNode ( 4 ) l3 = ListNode ( 2 ) l3 . next = ListNode ( 6 ) print ( Solution (). mergeKLists ([ l1 , l2 , l3 ])) print ( Solution (). mergeKLists ([])) print ( Solution (). mergeKLists ([[]])) ``` ### CPP ```cpp // OJ: https://leetcode.com/problems/merge-k-sorted-lists/ // Time: O(NlogK) // Space: O(K) class Solution { public: ListNode * mergeKLists ( vector < ListNode *>& lists ) { ListNode dummy , * tail = & dummy ; auto cmp = []( auto a , auto b ) { return a -> val > b -> val ; }; priority_queue < ListNode * , vector < ListNode *> , decltype ( cmp ) > q ( cmp ); for ( auto list : lists ) { if ( list ) q . push ( list ); // avoid pushing NULL list. } while ( q . size ()) { auto node = q . top (); q . pop (); if ( node -> next ) q . push ( node -> next ); tail -> next = node ; tail = node ; } return dummy . next ; } }; ```