2019-08-13 LeetCode148. 排序链表

链表的快排花了好久的时间。
1.quicksort结束的条件
2.将pivot改为head时候代码边界条件的改变
3.链表无法前推，end表示不可达到的节点

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        self.quicksort(head,None)
        return head

    def quicksort(self,head:ListNode,end:ListNode):
        if head==end or head.next==end :return   # 递归终点的考虑
        index = self.partition(head,end)
        self.quicksort(head,index)
        self.quicksort(index.next,end)

    def partition(self,head:ListNode,end:ListNode)->ListNode: #end是不可到的点
        if not head or head.next==end:return head
        small=head
        cur=head.next
        tmp=head.val
        while cur!=None and cur!=end: #end是不可到的点
            if cur.val<=tmp:
                small=small.next
                if small!=cur:self.swap(small,cur)
            cur=cur.next
        self.swap(small,head)  # 比较元素在head,small不能+1，+1后是大的，注意small可能没变，small-1不可行
        return small

    def swap(self,a:ListNode,b:ListNode):
        a.val,b.val=b.val,a.val