148. Sort List(链表的快速排序)

具体原理

https://blog.csdn.net/wumuzi520/article/details/8078322
自己的java实现：

class Solution {
    public void swap(ListNode a, ListNode b) {
        int tmp =a.val;
        a.val = b.val;
        b.val = tmp;
    }
    public void quick_sort(ListNode head,ListNode tail) {
        if(head!=tail){
        int pivot = head.val;
        ListNode p1 = head;
        ListNode p2 = p1.next;
        while(p2!=null&&p2!=tail) {
            if(p2.val<pivot) {
                p1 = p1.next;
                swap(p1,p2);
            }
            p2 = p2.next;
        }
        swap(head,p1);
        quick_sort(head,p1);
        quick_sort(p1.next,tail);
    }
    }
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        quick_sort(head,null);
        return head;
    }
}