Sort a linked list in O(n log n) time using constant space complexity.

Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5

class Solution {
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode mergeList(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while(head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                tail.next = head1;
                head1 = head1.next;
            } else {
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        if(head1 != null) tail.next = head1; 
        if(head2 != null) tail.next = head2; //接上head1或者head2后面的部分

        return dummy.next;
    }

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode mid = findMiddle(head);

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

        return mergeList(left, right);
    }
}


与上一致，最后sortlist里略不同，更好理解
class Solution {
    private 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;
    }

    private ListNode mergeList(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(0);
        ListNode elong = dummy;
        while(node1 != null && node2 != null) {
            if(node1.val <= node2.val) {
                elong.next = node1;
                node1 = node1.next;
            } else {
                elong.next = node2;
                node2 = node2.next;
            }
            elong = elong.next;
        }
        if(node1 != null) elong.next = node1;
        else elong.next = node2;

        return dummy.next;
    }

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;

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

        return mergeList(left, right);      
    }
}