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) {
        /**
        归并排序稳定O(NlogN), 但是容易出错, 需要注意细节
        **/
        return sort(head);
    }
    
    private ListNode sort(ListNode head) {
        // 用快慢指针找出中间节点并断开, 对断开后的两个链表分别排序后再合并
        if(head == null || head.next == null) return head;
        ListNode slow = head, fast = head, mid = head;
        while(fast != null && fast.next != null) {
            mid = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        mid.next = null;
        
        // head为左半部头节点, slow为右半部头结点
        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;
    }
}