A python solution using merge sort


  • 0
    G
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if len(lists) == 0:
            return None
        Solution.mergeSort(self, lists, 0, len(lists) - 1)
        return lists[0]
    def mergeSort(self, lists, p, r):
        if p < r:
            q = (p + r) / 2
            Solution.mergeSort(self, lists, p, q)
            Solution.mergeSort(self, lists, q + 1, r)
            Solution.mergeTwoParts(self, lists, p, q, r)
    def mergeTwoParts(self, lists, p, q,r ):
        node = Solution.mergeTwoLists(self, lists[p], lists[r])
        for i in range(p, r + 1):
            lists[i] = node
    def mergeTwoLists(self, l1, l2):
        """
        This function is from Merge Two Sorted Lists.
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 != None and l2 == None:
            return l1
        elif l1 == None and l2 != None:
            return l2
        elif l1 == None and l2 == None:
            return None
        if l1.val < l2.val:
            head = l1
        else:
            head = l2
        last = head
        while l1 != None and l2 != None:
            if l1.val < l2.val:
                last, l1 = l1, l1.next
            else:
                last.next, last, l2.next, l2 = l2, l2, l1, l2.next
        if l1 != None:
            last.next = l1
        else:
            last.next = l2
        return head

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.