Clean Python merge sort

  • 0
    def sortList(self, head):
        :type head: ListNode
        :rtype: ListNode
        if head is None:
            return None
        p,i = head,0
        while p:
            i += 1
            p =
        return self.mergeSort(head,i)[0]
    def mergeSort(self,head,k):
        if k == 1:
            next =
   = None
            return head,next
        left_head,next = self.mergeSort(head,k/2)
        right_head,next = self.mergeSort(next, k-(k/2))
        return self.merge(left_head,right_head),next
    def merge(self,h1,h2):
        dummy = ListNode(0)
        p = dummy
        while h1 and h2:
            if h1.val <= h2.val:
       = h1
                p =
                h1 =
       = h2
                p =
                h2 =
        if h1 is None and h2 is not None:
   = h2
        elif h2 is None and h1 is not None:
   = h1

Log in to reply

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