23.Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list.

Method 1 Divide and Conquer Nlog(k) time k is the number of linked lists, O(1) space.

• Pair up k lists and merge each pair.
• After the first merging, k lists are merged into k/2 lists with average of 2N/k length, then k/4, k/8 length and so on.
• Repeat this procedure until we get a final sorted list
• We can merge two sorted linked list in O(n)O(n) time where nn is the total number of nodes in two lists.

• class Solution(object):
    def mergeKLists(self, lists):
        if not lists:
            return None
        size = len(lists)
        if size == 1:
            return lists[0]
        if size == 2:
            return self.mergeTwoLists(lists[0], lists[1])
        return self.mergeTwoLists(self.mergeKLists(lists[:size/2]),self.mergeKLists(lists[size/2:]))
  
    def mergeTwoLists(self, l1, l2):
        res = ListNode(None)
        head = ListNode(None)
        res = head
        while l1 and l2:
            if l1.val <= l2.val:
                head.next = l1
                head = head.next
                l1 = l1.next
            else:
                head.next = l2
                head = head.next
                l2 = l2.next
        head.next = l1 if l1 else l2
        return res.next