CodeCollection2018
8/12/2019 - 12:58 AM

单链表快速排序

每次传入head和end指针。partition函数中，保持两个指针p和q，保持p到head之间的数都是小于等于head.val的，而p和q之间的数都是大于head.val的。如果q.val<had.val，则p=p.next，然后交换p和q的数值，之后再让q向后移动，只要q不等于end。循环退出之后交换head.val和p.val，然后返回p，将p作为下一个递归调用的end。

leetcode
content_copyfile_download
public ListNode ListPartition(ListNode head,ListNode end){
    if(head==end) return head;
    ListNode p = head;
    ListNode q = p.next;
    int key = head.val;
    while(q!=end){
        if(q.val < key){
            p = p.next;
            swap(p,q);
        }
        q = q.next;
    }
    swap(p,head);
    return q;
}
public void swap(ListNode p,ListNode q){
    int temp = p.val;
    p.val = q.val;
    q.val = temp;
}
public void quickSortOfList(ListNode head,ListNode end){
    if(head!=null){
        ListNode t = ListPartition(head,end);
        quickSortOfList(head,t);
        quickSortOfList(t.next,end);
    }
}