sort list

這題可以用 merge sort 或是 quick sort 來做，

用 merge sort 有一個要點是要先找到 list 的中間點，然後對左右各自 sort 最後 merge 起來

public ListNode sortList(ListNode head) {  
    // write your code here
    if (head == null || head.next == null) {
        return head;
    }

    ListNode mid = findMiddle(head);
    ListNode right = sortList(mid.next);
    mid.next = null;
    ListNode left = sortList(head);

    head = merge(left, right);
    return head;
}

public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head.next;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

public ListNode merge(ListNode left, ListNode right) {

    ListNode dummy = new ListNode(-1);
    ListNode newHead = null;
    while (left != null && right != null) {
        if (left.val < right.val) {
            dummy.next = left;
            left = left.next;
        } else {
            dummy.next = right;
            right = right.next;
        }

        if (newHead == null) {
            newHead = dummy.next;
        }
        dummy = dummy.next;
    }

    if (left != null) {
        dummy.next = left;
    }
    if (right != null) {
        dummy.next = right;
    }
    return newHead;
}