# Python quick sort solution easy to understand beats 95.51%

• 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):
"""
: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)

• @feather so genius. have an upvote

• @feather