148. Sort List

nlogn对于LIST来说只能是merge sort了。
quick sort没法倒退，不适用于singly list。

length < 3 手动排序
length >= 3，找到中间，前后分别排序，再merge，其实就是典型的merge sort + node management.

public class Solution 
{
    public ListNode sortList(ListNode head) 
    {
        if(head == null || head.next == null) return head;
        if(head.next.next == null)
        {
            if(head.val > head.next.val)
            {
                ListNode res = head.next;
                res.next = head;
                head.next = null;
                return res;
            }
            else return head;
        }
        ListNode slow = head;
        ListNode fast = head;

        while(fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next;
        slow.next = null;
        
        ListNode left = sortList(head);
        ListNode right = sortList(fast);
        ListNode dummy = new ListNode(-1);
        ListNode res = dummy;
        slow = left;
        fast = right;
        while(slow!=null && fast!=null)
        {
            if(slow.val < fast.val)
            {
                res.next = slow;
                res = res.next;
                slow = slow.next;
            }
            else
            {
                res.next = fast;
                res = res.next;
                fast = fast.next;
            }
        }
        if(slow == null) res.next = fast;
        else res.next = slow;
        
        return dummy.next;
        
    }
    

}

写的很垃圾，怎么快怎么来。。slow fast反复当做pointer使用。。