148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
     public ListNode sortList(ListNode head) {

        return head == null ? null : mergeSort(head);


    }

    private ListNode mergeSort(ListNode head) {
        if (head.next == null){
            return head;
        }

        ListNode s = head,f = head,pre = null;
        //找中点
        while (f != null && f.next != null){
            pre = s;
            f = f.next.next;
            s = s.next;
        }

        pre.next = null;//断开

        ListNode l = mergeSort(head);
        ListNode r = mergeSort(s);

        return merge(l,r);

    }
     //并
    private ListNode merge(ListNode l, ListNode r) {

        ListNode dummyHead = new ListNode(0);

        ListNode cur = dummyHead;

        while (l != null && r !=null){

            if (l.val < r.val){
                cur.next = l;
                cur = cur.next;
                l = l.next;
            }
            else {
                cur.next = r;
                cur = cur.next;
                r = r.next;
            }
        }

        //处理剩下的链表数据

        if (l != null){
            cur.next = l;
        }

        if (r != null){
            cur.next = r;
        }

        return dummyHead.next;

    }
}