LeetCode 148 自低向上归并

Question

老师你在<算法与数据结构>中的自低向上归并排序，是这样的

  /**
     * https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
     * @param arr
     * @param n   数组的长度下标
     */
    public static void sort(Comparable[] arr, int n) {

        for (int sz = 1; sz < n; sz = sz + sz) {//层级 分几次 logn 也就是2^0 2^1 2^2 2^3 1 2 4 8
            // 这里以排序数组7为例子(因为单数比较特殊 这里n=7和n=8一样)
            // 为什么边界时n-sz呢？ 当sz=1时 分成8份 n-sz=6  那么最后一个l下标是4 最后一个l应该是6 但是7个元素 最后一个不用归并了 推理可使用n=8上面
            // sz=2 n-sz=5  最后一个l是4
            // sz=4 n-sz=3  最后一个l是0
            // sz=8 n-sz=-1 结束排好序
            for (int i = 0; i < n-sz; i += sz + sz) {//找出每组的左右边界 i是左边界 每组l的值
                merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));
            }
        }
    }


    /**
     * 将arr[l...mid]和arr[mid+1...r]两部分进行归并
     * arr是原始数组 也就是我们最后排好序的数组
     * aux是临时数组 最后我们判断的是aux  输出的arr
     */
    private static void merge(Comparable[] arr, int l, int mid, int r) {


        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l;
        int j = mid + 1;

        //这里要注意 元数组是[l...mid]或arr[mid+1...r]  这里的l 和mid+1都可能不是0
        //但是我们添加的时候是从0可是添加的 所以在使用 aux的时候要有偏移
        for (int k = l; k <= r; k++) {

            // 如果左半部分元素已经全部处理完毕
            if (i > mid) {
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) { // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i - l];
                i++;
            } else //左边<右边  右边大放右边
                if (aux[i - l].compareTo(aux[j - l]) < 0) {// 左半部分所指元素 < 右半部分所指元素

                    //右边大 放左边
                    arr[k] = aux[i - l];
                    i++;

                } else {//左边>右边  左边大 或是左边和右边相等的时候 放左边 这样也可以保证归并排序的有序性
                    arr[k] = aux[j - l];
                    j++;
                }
        }

    }

我看了很多题解，发现大家可能实现不一样，但是都是这个思想。我想问的是 这个如何应用到链表上。题目说用常数的空间，但是我们归并是利用了一个临时空间。同时，<算法与数据结构>课程中说自底向上，没有用到索引，很适合遍历链表。那么有下面几个问题

1. 利用这个方式我应该遍历一遍链表的长度吧？l r k 这些也是索引吧
2. 很多题解 都说用cut切割 用prev和tail 然后交换 ，这也是我最不明白的，比如数组中：n=8 mid=1和5 1->2->4->5->3->6->7->8 i=0 j=4 然后i j谁小放入临时数组中最后完成排序 但是连表不行呀！常数空间 只能交换 但是一交换 指针一定错乱的。

因为归并我现在刚刚理解，而且这是我学的第一个归并写法 (有点先入为主，别的归并现在看还不舒服，估计以后孰能生巧会好很多吧) 希望老师能和我说明下这道题的 cut prev tail 这个方法 对于用这种方式去归并的代码如何用JAVA去解决这道题呢？ github上C++的实现有点看不懂。老师可以用java根据上面归并的方式实现嘛？

辛苦老师了，问题2是我最难困惑的，看了一天了 真的没办法只能来问老师了，知道老师比较忙，拜托了，辛苦

Answer 1

liuyubobobo 2020-04-16 15:26:51

以下回答基于我的代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0148-Sort-List/cpp-0148/main.cpp

1

是的，需要遍历链表长度。我的代码 69-74 在做这件事情。使用快慢指针找到链表的中间节点。基本原理是，快指针每次走两步；慢指针每次走一步。当快指针走到头的时候，慢指针指向的就是中间节点。

2

对于链表来说，根本不需要临时数组。p1 指向一个链表的开头；p2 指向另一个链表的开头。p 指向结果链表的最后一个节点，初始指向 dummyHead。

如果 p1 的值小于 p2，就可以直接将 p1 指向的节点连接到 p.next。然后 p1 指向下一个节点；p 指向下一个节点；

如果 p1 的值大于 p2，同理，可以直接将 p2 指向的节点连接到 p.next。然后 p2 指向下一个节点；p 指向下一个节点；

我的代码中，merge 函数就是在做这件事情。

==========

这个代码看 C++ 的代码非常简单，你不用理会所有的 * 符号。所以，

ListNode *p1 = a, *p2 = b, *p = dummyHead;，对应到 Java，就是：

ListNode p1 = a, p2 = b, p = dummyHead;

同时，所有的 ->，你理解成 Java 中的点就行。

所以 p->next，就是 p.next。

delete 不用管；NULL 是 Java 的 null；非常好翻译成 Java 的。

看看能不能理解？

加油！：）

• 提问者 慕妹2978617 #1

  老师的回答真的速度太快了，我现在去看看，买你您的2个课程，实在太好了，就是我非科班转来看的有些吃力，因为课程太好，3个课程都有买，因为面试比较急所以没办法全买，等我找到工作一定把老师的课程全买了。谢谢老师

• liuyubobobo 回复 提问者 慕妹2978617 #2

  按需购买就好。非科班的话建议先好好学《玩转数据结构》。找工作刷一刷 Leetcode，但其实链表的归并排序被问到的概率还是蛮小的，本身也确实有一些难度，我觉得可以先放一放。把这个课程涉及的题目类型的基本概念先过一遍，然后慢慢刷题：）另外，看你的目标是不是大厂，如果不是大厂，可能也不需要刷太多算法问题。面试不仅仅考算法，切记。看一看你的目标企业的面经。加油！

• 提问者 慕妹2978617 回复 liuyubobobo #3

  每个程序员都有个大厂梦，算法基础一直是我的弱项，我是Android开发，其实我觉得，Android面试其实就是 java基础，网络，和一些源码和开源库源码，项目经历，其实这些觉得为了面试找找看看记一记时间比较快，问的都是流程，但是我觉得正好趁面试，语言基础，网络基础，算法基础这些我比较看重(操作系统我也看重，但是没时间了，陌生领域)，用不到学一下也能有个印象充实自己，算法2个月其他所有2个月，哈哈，然后大厂我想试试。感觉老师像个朋友，说的有点多。谢谢老师，祝你漂泊海外，身体健康
  ，疫情期间保护好自己，加油！

点开查看后面1条评论