題意：給一個亂序的鏈表，把它排序輸出

思路：

1. 找出二分鏈表的節(jié)點
2. 對每一半進行遞歸排序
3. 把拍好序的兩半merge到一個，并返回

思想：歸并排序

復(fù)雜度：時間O（nlgn)，空間O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        
        ListNode n1 = newhead;
        ListNode n2 = newhead;
        while(n1 != null && n1.next != null) {
            n1 = n1.next.next;
            n2 = n2.next;
        }
        n1 = n2.next;
        n2.next = null;

        n1 = sortList(n1);
        n2 = sortList(newhead.next);

        newhead = new ListNode(0);
        ListNode runner = newhead;
        while(n1 != null && n2 != null) {
            if(n1.val < n2.val) {
                ListNode temp = n1.next;
                n1.next = null;
                runner.next = n1;
                runner = n1;
                n1 = temp;
            } else {
                ListNode temp = n2.next;
                n2.next = null;
                runner.next = n2;
                runner = n2;
                n2 = temp;
            }
        }
        if(n1 != null)
            runner.next = n1;
        if(n2 != null)
            runner.next = n2;
        return newhead.next;
    }
}