Python quick sort solution easy to understand beats 95.51%

  • 1

    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 =
                pivotPrev =
       = end
                pivotPost = pivotPrev
                while node != end:
                    temp =
                    if node.val > pivotPrev.val:
               = node
                    elif node.val < pivotPrev.val:
               = node
               = node
                        pivotPost =
                    node = temp
                return [pivotPrev, pivotPost]
            def quicksort(start, end):
                if != end:
                    prev, post = partition(start, end)
                    quicksort(start, prev)
                    quicksort(post, end)
            newHead = ListNode(0)
   = head
            quicksort(newHead, None)

  • 0

    @feather so genius. have an upvote

  • 0

    quicksort(newHead, None)

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

  • 0

    @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.