Sort List leetcode

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

分析： O(nlogn)就是用merge sort或者quick sort

用merge sort首先考虑找中点---用快慢指针的方法

merge-- 用merge 2 linkedlist方法

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode mid = findmid(head);
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);
        return merge(left, right);
    }
    private ListNode findmid(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    private ListNode merge(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;
                tail = tail.next;
                head1 = head1.next;
            } else {
                tail.next = head2;
                tail = tail.next;
                head2 = head2.next;
            }
        }
        if (head1 != null){
            tail.next = head1;
        } else {
            tail.next = head2;
        }
        return dummy.next;
    }
}