Merge k Sorted Lists

Hard

#0023Time: O(k * N)Space: O(1)41 companies

Algorithms

Divide and Conquer Merge Sort

Data structures

Linked List Heap (Priority Queue)

Companies

Adobe Airbnb Amazon Apple

Prompt

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 <= 10⁴
0 <= lists[i].length <= 500
-10⁴ <= lists[i][j] <= 10⁴
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 10⁴.

Approaches

4 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode mergeKLists(ListNode[] lists) {13        if (lists == null || lists.length == 0) {14            return null;15        }16        17        ListNode mergedList = lists[0];18        for (int i = 1; i < lists.length; i++) {19            mergedList = mergeTwoLists(mergedList, lists[i]);20        }21        22        return mergedList;23    }24 25    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {26        ListNode dummyHead = new ListNode(0);27        ListNode current = dummyHead;28        29        while (l1 != null && l2 != null) {30            if (l1.val < l2.val) {31                current.next = l1;32                l1 = l1.next;33            } else {34                current.next = l2;35                l2 = l2.next;36            }37            current = current.next;38        }39        40        if (l1 != null) {41            current.next = l1;42        } else {43            current.next = l2;44        }45        46        return dummyHead.next;47    }48}

Complexity

Time

O(k * N)

Space

O(1)

Trade-offs

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.

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.

Algorithm

Create a list, e.g., ArrayList<Integer>, 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.

Walkthrough

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.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11import java.util.ArrayList;12import java.util.Collections;13import java.util.List;14 15class Solution {16    public ListNode mergeKLists(ListNode[] lists) {17        List<Integer> allValues = new ArrayList<>();18        for (ListNode head : lists) {19            ListNode current = head;20            while (current != null) {21                allValues.add(current.val);22                current = current.next;23            }24        }25        26        Collections.sort(allValues);27        28        ListNode dummyHead = new ListNode(0);29        ListNode current = dummyHead;30        for (int val : allValues) {31            current.next = new ListNode(val);32            current = current.next;33        }34        35        return dummyHead.next;36    }37}

Complexity

Time

O(N log N)

Space

O(N)

Trade-offs

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.

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.

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.

Walkthrough

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.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11import java.util.PriorityQueue;12 13class Solution {14    public ListNode mergeKLists(ListNode[] lists) {15        if (lists == null || lists.length == 0) {16            return null;17        }18        19        // Min-heap to store the head of the lists20        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);21        22        // Add the head of each list to the min-heap23        for (ListNode head : lists) {24            if (head != null) {25                minHeap.add(head);26            }27        }28        29        ListNode dummyHead = new ListNode(0);30        ListNode current = dummyHead;31        32        // Process nodes from the heap33        while (!minHeap.isEmpty()) {34            // Get the node with the smallest value35            ListNode smallestNode = minHeap.poll();36            37            // Add it to the merged list38            current.next = smallestNode;39            current = current.next;40            41            // If there is a next node in the list, add it to the heap42            if (smallestNode.next != null) {43                minHeap.add(smallestNode.next);44            }45        }46        47        return dummyHead.next;48    }49}

Complexity

Time

O(N log k)

Space

O(k)

Trade-offs

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.

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.

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.

Walkthrough

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.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode mergeKLists(ListNode[] lists) {13        if (lists == null || lists.length == 0) {14            return null;15        }16        return merge(lists, 0, lists.length - 1);17    }18 19    private ListNode merge(ListNode[] lists, int start, int end) {20        if (start == end) {21            return lists[start];22        }23        if (start > end) {24            return null;25        }26        27        int mid = start + (end - start) / 2;28        ListNode l1 = merge(lists, start, mid);29        ListNode l2 = merge(lists, mid + 1, end);30        31        return mergeTwoLists(l1, l2);32    }33 34    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {35        ListNode dummyHead = new ListNode(0);36        ListNode current = dummyHead;37        38        while (l1 != null && l2 != null) {39            if (l1.val < l2.val) {40                current.next = l1;41                l1 = l1.next;42            } else {43                current.next = l2;44                l2 = l2.next;45            }46            current = current.next;47        }48        49        if (l1 != null) {50            current.next = l1;51        } else {52            current.next = l2;53        }54        55        return dummyHead.next;56    }57}

Complexity

Time

O(N log k)

Space

O(log k)

Trade-offs

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.

Solutions

Solution

1/** * 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 ; } }

1public 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 ; } }

1/** * 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 =2  function (lists) {3    const n = lists.length;4    if (n == 0) {5      return null;6    }7    for (let i = 1; i < n; ++i) {8      lists[i] = mergeTwoLists(lists[i - 1], lists[i]);9    }10    return lists[n - 1];11  };12function mergeTwoLists(l1, l2) {13  const dummy = new ListNode();14  let cur = dummy;15  while (l1 && l2) {16    if (l1.val <= l2.val) {17      cur.next = l1;18      l1 = l1.next;19    } else {20      cur.next = l2;21      l2 = l2.next;22    }23    cur = cur.next;24  }25  cur.next = l1 || l2;26  return dummy.next;27}

1# 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 ([[]]))

1// 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 ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1/** * 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 ; } }

1public 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 ; } }

1/** * 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 =2  function (lists) {3    const n = lists.length;4    if (n == 0) {5      return null;6    }7    for (let i = 1; i < n; ++i) {8      lists[i] = mergeTwoLists(lists[i - 1], lists[i]);9    }10    return lists[n - 1];11  };12function mergeTwoLists(l1, l2) {13  const dummy = new ListNode();14  let cur = dummy;15  while (l1 && l2) {16    if (l1.val <= l2.val) {17      cur.next = l1;18      l1 = l1.next;19    } else {20      cur.next = l2;21      l2 = l2.next;22    }23    cur = cur.next;24  }25  cur.next = l1 || l2;26  return dummy.next;27}

1# 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 ([[]]))

1// 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 ; } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.