# [python]Sort List LTE

• ``````class Solution:
# @return a ListNode
less = None
greater = None

while None != node:
tmp = node.next
if pivot.val > node.val:
node.next = less
less = node
else:
node.next = greater
greater = node
node = tmp

less = self.sortList(less)
if less != None:
node = less
while node.next != None:
node = node.next
node.next = pivot
else:
less = pivot

greater = self.sortList(greater)
pivot.next = greater

return less``````

• i got it,if there are many numbers which are the same in the list, the code will waster too much time to handle it .

• ``````class Solution:
# @return a ListNode
less_list    = None
greater_list = None
equal_list   = pivot

while None != node:
tmp = node.next
if pivot.val > node.val:
node.next = less_list
less_list = node
elif pivot.val < node.val:
node.next = greater_list
greater_list = node
else:
equal_list.next = node
equal_list = node
node = tmp
#greater_list指向等于pivot的链表
equal_list.next = None
#less_list指向小于pivot的链表
less_list = self.sortList(less_list)
#greater_list指向大于pivot的链表
greater_list = self.sortList(greater_list)
less_list = self.connect(less_list, pivot, greater_list)

return less_list

def connect(self, less_list, pivot, greater_list):
node = pivot
while True:
if node.next == None:
node.next = greater_list
break
node = node.next

node = less_list
if less_list == None:
less_list = pivot
else:
while node.next != None:
node = node.next
node.next = pivot
return less_list``````

• on the last part of 'connect', I think the while loop will result in a O(n^2) in the worst case. Am I right?

• yes,quick sort will be O(n^2) in the worst case which less than pivot was empty and greater than pivot was full.

• in your code, it the 'less than pivot' list that causes the worst case.

• absolutely yes, i can choose pivot by ramdon to eliminate this case.

• i don't think randomize the pivot will help the last while loop in 'connect'.
Btw, you can use 'equal_list.next = great_list' to replace the first while loop

• you mean:
def connect(self, less_list, pivot, equal_list, greater_list):
equal_list.next = greater_list
node = less_list
if less_list == None:
less_list = pivot
else:
while node.next != None:
node = node.next
node.next = pivot
return less_list

right?

• that is what I meant

• thank you!you are right.

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