Quick sort / Merge sort / Python


  • 2
    class Solution(object):
        def sortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            
            # return self.mergeSort(head)   # to use mergeSort
            return self.quickSort(head)[0].next
            
            
        def quickSort(self, head):
    
            link_small, link_equal, link_large = ListNode(0), ListNode(0), ListNode(0)
            small_end, equal_end, large_end = link_small, link_equal, link_large
            
            equal_end.next = head
            if not head:
                return link_equal, equal_end
            equal_end, head = equal_end.next, head.next
    
            while head:
                if head.val>equal_end.val:
                    large_end.next = head
                    large_end = large_end.next
                elif head.val<equal_end.val:
                    small_end.next = head
                    small_end = small_end.next
                else:
                    equal_end.next = head
                    equal_end = equal_end.next
                    
                head = head.next
                    
            large_end.next = small_end.next = equal_end.next = None
            
            small_sorted, small_end = self.quickSort(link_small.next)
            large_sorted, large_end = self.quickSort(link_large.next)
            
            small_end.next = link_equal.next
            equal_end.next = large_sorted.next
            
            return small_sorted, (large_end if large_sorted!=large_end else equal_end) # return the pre-first and last node of sorted list
            
            
        def mergeSort(self, head):
            if not head or (head and not head.next):
                return head
            
            # divide
            slowN, fastN = head, head.next
            while fastN and fastN.next:
                slowN, fastN = slowN.next, fastN.next.next
                
            halfN, slowN.next = slowN.next, None
            h1, h2 = self.mergeSort(head), self.mergeSort(halfN)
            
            # merge
            head_sorted = ListNode(0)
            end_sorted = head_sorted
            while h1 and h2:
                if h1.val<h2.val:
                    end_sorted.next = h1
                    h1 = h1.next
                else:
                    end_sorted.next = h2
                    h2 = h2.next
                end_sorted = end_sorted.next
            if h1:
                end_sorted.next = h1
            else:
                end_sorted.next = h2
            return head_sorted.next
            
    

Log in to reply
 

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