MergeKSortedArray.py

# Question link - https://leetcode.com/problems/merge-k-sorted-lists/description/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # Base case
        if not lists or len(lists) == 0:
            return None
    
        # Divide and conquer approch , by using the merge two list
        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.mergeTwoLists(l1 , l2))
            lists = mergedLists
        return lists[0]

       
    
    # Helper function to merge two list 
    def mergeTwoLists(self , l1 , l2):
        tail = dummy = ListNode()
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        if l1:
            tail.next = l1
        if l2:
            tail.next = l2

        return dummy.next