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
@feather so genius. have an upvote
Thank you for your solution!
Could you explain this line of your code?
@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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.