Nlog(N)时间复杂度排序链表

class Solution {
    public ListNode sortList(ListNode head) {

        if (head == null || head.next == null){
            return head;
        }

        ListNode newHead = new ListNode(0);
        newHead.next = head;

        quickSort(newHead, null);

        return newHead.next;
    }

    private void quickSort(ListNode head, ListNode tail){

        if (head.next == tail || head.next.next == tail){
            return;
        }

        ListNode firstNode = head.next;

        ListNode pl = firstNode;
        ListNode pr = firstNode;
        ListNode p = firstNode.next;
        int flagVal = firstNode.val;

        for (;p != tail;){
            ListNode pNext = p.next;
            p.next = null;
            if (p.val < flagVal){
                p.next = pl;
                pl = p;
            } else {
                pr.next = p;
                pr = p;
            }
            p = pNext;
        }

        head.next = pl;
        pr.next = tail;

        quickSort(head, firstNode);
        quickSort(firstNode, tail);
    }
}