算法之排序链表-归并排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        return sort (head);
    }
    private ListNode sort(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode slow =head, fast = head,pre = head;
        while(fast!= null && fast.next!= null) {
            pre = slow;                //非常重要！ 需要中点的前一个指针截断
            fast = fast.next.next;
            slow = slow.next;
        }
        pre.next = null;
        ListNode lhead = sort(head);
        ListNode rhead = sort(slow);
        return merge(lhead,rhead);
    }
    private ListNode merge(ListNode lhead, ListNode rhead) {
        ListNode head = new ListNode(0);             //非常重要，需要记录住每次排序后的节点
        ListNode cur = head;
        while(lhead!= null && rhead != null) {
            if(lhead.val <= rhead.val) {
                cur.next = lhead;
                lhead = lhead.next;
            }
            else {
                cur.next = rhead;
                rhead = rhead.next;
            }
            cur = cur.next;
        }
        if(lhead != null)
            cur.next = lhead;
        if(rhead != null)
            cur.next = rhead;
        return head.next;
    }
}