23. Merge k Sorted Lists — LeetCode(Python)

I got you!

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.

Solution:

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0:
            return None
        
        while len(lists) > 1:
            mergedLists = []
            
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i+1] if (i+1) < len(lists) else None
                mergedLists.append(self.mergeLists(l1, l2))
            
            lists = mergedLists
        
        return lists[0]
    
    def mergeLists(self, l1, l2):
        dummy = curr = ListNode()
        
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
            
        curr.next = l1 or l2
            
        return dummy.next

Explanation:

The trick that we use here is to break this problem into a simpler problem.

We pick two lists at once and merge them and append to our given list of lists.

This is done until there is only one list left in the list of lists, which is our answer.

See Merge Two Sorted Lists to get more deep into the mergeLists() function.

The rest of the code is pretty intuitive.

Time and Space Complexity —

Since we are iterating over the alternate list in the list of lists, we require linear time for that operation.

Also, we require linear time to merge two lists and logarithmic time to merge n lists.

And we require a constant amount of extra space.

Thus, if k is the number of lists in lists, and N is the total number of nodes, or n is the average length of each list,

Time Complexity: O(N log(k)) or O(nk log(k))

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏