python quicksort 95th percentile


  • 0
    T
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def sortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not (head and head.next):
                return head
            l = None
            r = None
            p = head
            head = head.next
            p.next = None
            while head:
                c = head
                head = head.next
                c.next = None
                if c.val < p.val:
                    c.next = l
                    l = c
                elif c.val > p.val:
                    c.next = r
                    r = c
                else:
                    c.next = p
                    p = c
            l = self.sortList(l)
            r = self.sortList(r)
            pf = p
            while p.next:
                p = p.next
            p.next = r
            if l:
                head = l
                while l.next:
                    l = l.next
                l.next = pf
                return head
            return pf
    

    this uses duplicate skipping (keeps duplicates of the pivot with the pivot), otherwise a pretty unremarkable quicksort.


Log in to reply
 

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