Python quick sort solution easy to understand beats 95.51%


  • 1
    F

    To solve the TLE problem, I set two pivots in the partition function, pivotPrev and pivotPost. We just pick the first element as pivot. And if we encounter a node with the same value as pivotPrev, we move the pivotPost one step forward. When partition function returns, the pivotPrev becomes the end node for the former half while the pivotPost becomes the start node for the latter half. In this way, we don't have to sort nodes between two pivots in the next round.

    For example, input like 2-3-2-1-4-6-2-5 will become 1-2-2-2-5-6-4-3, and the partition function returns the first node with value 2 and the last node with value 2, then we only have to sort 1 and 5-6-4-3 respectively.

    class Solution(object):
        def sortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            def partition(start, end):
                node = start.next.next
                pivotPrev = start.next
                pivotPrev.next = end
                pivotPost = pivotPrev
                while node != end:
                    temp = node.next
                    if node.val > pivotPrev.val:
                        node.next = pivotPost.next
                        pivotPost.next = node
                    elif node.val < pivotPrev.val:
                        node.next = start.next
                        start.next = node
                    else:
                        node.next = pivotPost.next
                        pivotPost.next = node
                        pivotPost = pivotPost.next
                    node = temp
                return [pivotPrev, pivotPost]
            
            def quicksort(start, end):
                if start.next != end:
                    prev, post = partition(start, end)
                    quicksort(start, prev)
                    quicksort(post, end)
    
            newHead = ListNode(0)
            newHead.next = head
            quicksort(newHead, None)
            return newHead.next

  • 0
    M

    @feather so genius. have an upvote


  • 0
    B

    @feather
    quicksort(newHead, None)

    Thank you for your solution!
    Could you explain this line of your code?


  • 0
    F

    @baisheng The first parameter and the second element are the bounds of the list to be sorted, you can see them to be sentinel elements. Initially we create an element before the list, and notice that the last element of the list is Null. So we can sort elements between these two elements.


Log in to reply
 

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