Quick sort, O(NlogN) time, O(1) space


  • 0
    O

    I have implemented the quick sort version, time complexity O(NlogN), space O(1).

        def sortList(self, head: ListNode, untilNone):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            def sort(head, until=None):
                '''
                Sort the list from head until `until`.
                '''
                if head == until:
                    return head
                dummy = ListNode(None)
                dummy.next = head
    
                pivot = head.val
                smaller = dummy
                equal = dummy.next
                while equal.next not in (None, until) and equal.next.val == equal.val:
                    equal = equal.next
                prev = equal
                p = prev.next
                while p not in (None, until):
                    if p.val < pivot:
                        prev.next = p.next
                        p.next = smaller.next
                        smaller.next = p
                        smaller = p
                    elif p.val == pivot and equal.next != p:
                        prev.next = p.next
                        p.next = equal.next
                        equal.next = p
                        equal = p
                    else:
                        prev = p
                    p = prev.next
    
                dummy.next = sort(dummy.next, smaller.next)
                equal.next = sort(equal.next, until)
                return dummy.next
    
            return sort(head)
    

Log in to reply
 

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