排序链表

148.排序链表

题意

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

思路

题目要求时间空间复杂度分别为 $O(nlogn)$ 和 $O(1)$，自然想到二分，从而联想到归并排序。

归并排序详情：归并排序

使用快慢指针 fast 和 slow，找到中间结点后，先递归再合并。

1. 确定分界点：

   • 归并每次都将中点作为分界点，将整个序列分为两部分；
   • 找到中点 slow 后，保存右半部分的头结点 slow.next，执行 slow.next = null 将链表分割；
   • 当 head.next == null 时，说明只有一个结点了，直接返回此结点。

2. 递归排序：

   • 建立临时结点 tmp 作为临时链表头部，从头开始遍历比较，每次比较 left 和 right，将小的结点接入临时链表后面；
   • 如果有一部分遍历完了，而另一部分还有剩余，则将剩余那部分直接接在临时链表后面；
   • 返回临时链表头结点。

代码

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        // 快慢指针找到中间结点
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        // 将链表断开，分割成两部分
        ListNode slowNext = slow.next;
        slow.next = null;

        // 递归排序左右两部分
        ListNode left = sortList(head);
        ListNode right = sortList(slowNext);

        // 合并排序后的两部分
        ListNode tmp = new ListNode(0);
        ListNode dummp = tmp;
        while (left != null && right != null){
            if (left.val < right.val){
                tmp.next = left;
                left = left.next;
            }
            else {
                tmp.next = right;
                right = right.next;
            }
            tmp = tmp.next;
        }

        // 把剩余部分接上
        tmp.next = left == null ? right : left;

        return dummp.next;  // 返回头结点
    }
}