【Leetcode】链表排序（逐步提高时空复杂度）

面试遇到的一道题，链表排序。

链表排序

1. 题目描述

leetcode题目链接：148. 排序链表

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

2. 思路分析

这道题考虑时间复杂度优于 O(n2) 的排序算法。题目的进阶问题要求达到 O(nlog⁡n)的时间复杂度和 O(1) 的空间复杂度，时间复杂度是 O(nlog⁡n) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n2)，其中最适合链表的排序算法是归并排序。

方法一：堆排序

最简单直接的方法：

1. 定义类型为ListNode的最小堆
2. 建堆：链表所有node入堆
3. 依次弹出堆顶node，即是从小到大的顺序
4. 时间复杂度O(nlogn)，空间复杂度O(n)
5. 此法和数组的堆排序几乎没有区别，实现起来最简单，不易出错

方法二：自顶向下归并排序

优化空间复杂度。

对链表自顶向下归并排序的过程如下。

1. 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
2. 对两个子链表分别排序。
3. 将两个排序后的子链表合并，得到完整的排序后的链表。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。

复杂度分析

• 时间复杂度：O(nlog⁡n)，其中 n 是链表的长度。
• 空间复杂度：O(log⁡n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。

方法三：自底向上归并排序

进一步优化空间复杂度。

空间复杂度 O(1)。从单个节点开始两两合并成多段有序链表；将多段有序链表再两两合并，直到合并成一个完整链表。

3. 代码实现

方法一：堆排序

class Solution {
    
    public ListNode sortList(ListNode head) {
    
        // 堆排序
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);  // 小顶堆
        while (head != null) {
      // 全部加入小顶堆
            queue.offer(head);
            head = head.next;
        }
        // 出堆，赋值给新的链表
        ListNode dumpy = new ListNode();
        ListNode cur = dumpy;
        while (queue.size() > 0) {
    
            cur.next = queue.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dumpy.next;

    }
}

方法二：自顶向下归并排序

class Solution {
    
    public ListNode sortList(ListNode head) {
    
        // 如果链表为空，或者只有一个节点，直接返回，不用排序
        if (head == null || head.next == null)  return head;

        // 快慢双指针移动，寻找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
    
            fast = fast.next.next;
            slow = slow.next;
        }
        // 找到中间节点，slow节点的next指针指向mid
        ListNode mid = slow.next;
        // 切断链表
        slow.next = null;
        // 排序左子链表
        ListNode left = sortList(head);
        // 排序右子链表
        ListNode right = sortList(mid);
        // 合并链表
        return merge(left, right);
    }
    public ListNode merge(ListNode left, ListNode right) {
    
        ListNode head = new ListNode(0);
        ListNode tmp = head;
        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;
        }
        if (left != null) {
    
            tmp.next = left;
        } else if (right != null) {
    
            tmp.next = right;
        }
        return head.next;
    }
}