148. 排序链表

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

思路

此题为链表的归并排序
1 使用快慢指针法找到链表的中间节点
2 然后断开链表，两个链表分别递归排序
3 将两个有序的链表归并成一个有序链表

代码

class Solution {
    //归并排序
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode sentinal = new ListNode(0, head);
        ListNode p1 = sentinal;
        ListNode p2 = sentinal;
        while (p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
        }
        //p1为中间节点
        p2 = p1.next;
        p1.next = null;
        //两边递归再归并
        ListNode cur1 = sortList(head);
        ListNode cur2 = sortList(p2);
        ListNode nxt1 = cur1.next;
        ListNode nxt2 = cur2.next;
        sentinal.next = null;
        ListNode newTail = sentinal;
        while (cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                newTail.next = cur1;
                cur1 = nxt1;
                if (nxt1 != null) {
                    nxt1 = nxt1.next;
                }
            }else {
                newTail.next = cur2;
                cur2 = nxt2;
                if (nxt2 != null){
                    nxt2 = nxt2.next;
                }
            }
            newTail = newTail.next;
        }
        if (cur1 != null){
            newTail.next = cur1;
        }
        if (cur2 != null){
            newTail.next = cur2;
        }
        return sentinal.next;
    }
}