当前位置：网站首页>LeetCode-归并排序链表

LeetCode-归并排序链表

2022-07-02 04:23:00 【Master_hl】

题目描述

示例分析

题目要求

一看见时间复杂度为O(N*logN)，而处于这个时间复杂度的排序只有三个：堆排、快排、归并排序，快排最坏情况下，是O(N^2)，而堆排不适合链表的排序，所以只剩下归并排序了。

方法一：自顶而下（递归）

自顶而下的方式，就是将链表在递出去的过程中不断拆分成两半，直到只剩下最后两个结点的时候才开始归回来合并，在归回来的时候，左右两个序列段都已经分别有序了，所以合并过程就是将两个有序序列段合并。但是这样做还是达不到完成这个题的要求，这里只是提供一种递归的思路，后面会给出迭代的思路。

代码实现

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        //快慢指针来分割链表
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode midR = slow.next;
        slow.next = null;//将中间结点置空是下次递归 return 的必要条件
        ListNode left = sortList(head);
        ListNode right = sortList(midR);
        //合并
        ListNode newHead = new ListNode(0);
        ListNode prev = newHead;;
        while(left != null && right != null) {
            if(left.val <= right.val) {
                prev.next = left;
                left = left.next;
            } else {
                prev.next = right;
                right = right.next;
            }
            prev = prev.next;
        }
        //走到这里，两个有序序列，一个为空，一个不为空，把不为空的接在prev的后面
        prev.next = (left != null ? left : right);
        return newHead.next;
    }

画图分析

上图分析了左半部分递出去的过程，2和5合并完之后成为一个有序序列段，而 midR 这一边是一个单独的只有一个结点的有序序列段，所以就印证了前面的解释。

复杂度分析

时间复杂度：O(N*logN) ，就是归并排序的时间复杂度。
空间复杂度：O(logN)，每一层的合并都用到了辅助结点，所以空间复杂度就是树的高度。

方法二：自底而上（迭代）

自顶而下为什么做不到常数个空间的空间复杂度呢，因为每递归一次，就要开辟一个辅助的栈空间，并且先执行一个函数的左，右边还没执行，所以栈空间就没有被回收，就必然导致空间复杂度较迭代来说要高。迭代的方式不像递归那样先操作整条链表，再不断细分，而是先两两有序，再四个四个有序...，最后当subLen = 链表长度的一半时，执行完本次循环，就全部有序。

代码实现

    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        int len = 0;
        ListNode node = head;
        while (node != null) {
            len++;
            node = node.next;
        }
        ListNode newHead = new ListNode(0, head);
        //每次循环不断让左右序列扩大两倍
        for (int subLen = 1; subLen < len; subLen <<= 1) {
            ListNode prev = newHead;
            ListNode cur = newHead.next;
            while (cur != null) {
                ListNode head1 = cur;
                //移动到左子序列的尾巴
                for (int i = 1; i < subLen && cur.next != null; i++) {
                    cur = cur.next;
                }
                ListNode head2 = cur.next;
                //分割
                cur.next = null;
                cur = head2;
                //移动到右子序列的尾巴
                for (int i = 1; i < subLen && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }
                //用next记录下一次待合并的两序列中左序列的头
                ListNode next = null;
                if (cur != null && cur.next != null) {
                    next = cur.next;
                    cur.next = null;
                }
                ListNode merged = merge(head1, head2);
                //将合并的序列串在辅助结点之后
                prev.next = merged;
                while (prev.next != null) {
                    prev = prev.next;
                }
                cur = next;
            }