题解 | #单链表的排序#

quicksort

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        # write code here
        if not head or not head.next:
            return head
        a,b = self.quick_sort(head)
        return a 
    
    def quick_sort(self,head):
        if not head :
            return (None,None)
        if not head.next:
            return (head,head)
        mid = head
        left_head = ListNode(-1)
        left_tail = left_head
        right_head = ListNode(-1)
        right_tail = right_head
        temp = mid.next
        while temp:
            new_temp = temp.next
            if temp.val <= mid.val:
                left_tail.next = temp
                left_tail = left_tail.next
            else:
                right_tail.next = temp
                right_tail = right_tail.next
            temp = new_temp
        left_tail.next = None
        right_tail.next = None
        left_head,left_tail = self.quick_sort(left_head.next)
#         print(right_head.next.val)
        right_head,right_tail = self.quick_sort(right_head.next)
#         print(left_head)
#         print(right_head)
        mid.next = right_head
        if not left_head or not left_tail:
            if not right_head or not right_tail:
                return (mid,mid)
            else:
                return (mid,right_tail)
        else:
            left_tail.next = mid
            if not right_tail:
                return (left_head,mid)
            else:
                return (left_head,right_tail)