0023. Merge k Sorted Lists

Hard | Linked List + Sort | 76 ms (98.81%), 22.3 MB (39.22%)

❓ Problem Statement

Source: LeetCode - Merge k Sorted Lists GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

Constraints:

• k == lists.length

• 0 <= k <= 10^4

• 0 <= lists[i].length <= 500

• -10^4 <= lists[i][j] <= 10^4

• lists[i] is sorted in ascending order.

• The sum of lists[i].length won't exceed 10^4.

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

Input: lists = []
Output: []

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

💡 Ideas

Extended question from LeetCode 0021. Merge Two Sorted Lists.

We could use the "Merge with Divide and Conquer" method for better performance. Generally speaking, we do merge starting with 2 lists per iteration, then increasing to 4 lists per iteration, etc.

🎨 Diagram Explanation

# size = 1, len = 5
# for i in range(0, len - size, size * 2)
# i = 0, 2, 4
# merge input = [0, 1] [2, 3] [4, 5]
['l0', l1, 'l2', l3, 'l4']
   |  /      |  /      |
   | /       | /       |
   |/        |/        |
   l0        l2       l4

# size = 2, len = 5
# for i in range(0, len - size, size * 2)
# i = 0
# merge input = [0, 2]
['l0', l1, l2, l3, l4]
   |        /       |
   |-------*        |
   l0              l4
   
# size = 4, len = 5
# for i in range(0, len - size, size * 2)
# i = 0
# merge input = [0, 4]
['l0', l1, l2, l3, l4]
   |                /
   |---------------*
   l0

🤖 Python3

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # (base case)
        if len(lists) == 0: return None
        if len(lists) == 1: return lists[0]
        
        # ==================================================
        #  Linked List + Sort                              =
        # ==================================================
        # time  : O(nlogk)
        # space : O(1)
        # 
        # n is the total number of nodes in two linked lists
        # k is the number of linked lists
        
        size = 1
        while size < len(lists):
            for i in range(0, len(lists) - size, size * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i+size])
            size *= 2
            
        return lists[0]
        
    def merge2Lists(self, l1: ListNode, l2: ListNode) -> ListNode:
        ret = ListNode(0)
        cur = ret
        
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = ListNode(l1.val)
                cur = cur.next
                l1 = l1.next
            else:
                cur.next = ListNode(l2.val)
                cur = cur.next
                l2 = l2.next
                
        cur.next = l1 or l2
                
        return ret.next

🤖 Java

class Solution {
    /**  
     * @time  : O(nlogk)
     * @space : O(1)
     */

    public ListNode mergeKLists(ListNode[] lists) {
        /* base case */
        if(lists.length == 0) return null;
        if(lists.length == 1) return lists[0];
        
        int size = 1;
        while(size < lists.length) {
            for(int i=0 ; i<lists.length-size ; i+=size*2) {
                lists[i] = merge2Lists(lists[i], lists[i+size]);
            }
            size *= 2;
        }
        return lists[0];
    }
    
    public ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode(0);
        ListNode cur = ret;
        
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            cur = cur.next;
        }
        
        cur.next = (l2 == null) ? l1 : l2;
        
        return ret.next;
    }
}