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

  /**
     * 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是我最难困惑的，看了一天了 真的没办法只能来问老师了，知道老师比较忙，拜托了，辛苦