哪个是在递归递归链接列表时首先出现的？

Question

因此，我正在Java学习DSA，并扭转了链接列表。我理解了迭代方法，但是在学习递归方法的同时，递归有两件事的时间点：

1. 将链接转换
2. 为列表底部的链接并确定新的Head

Q1。哪个是第一个？（请一步一步） 堆栈被穿过底部，在上升时，堆栈会逆转链接，并返回新的头部，或者链接在其底部和到达时逆转，将新的头部返回到顶部。

Q2。如何将新节点返回到上方的递归（请逐步）？

如果我理解错误的话，有人可以向我解释递归如何深入起作用吗？不仅是说将其留给信仰的递归飞跃。我想完整地理解它及其步骤。

Answer 1

• Q1：将列表横穿到末端，并在堆栈上保留反向链接，将新的头部返回到顶部。 （另一种方式也可以参见下面的输出后面。）

• Q2：这个想法始终是返回新的头部，但不要立即返回。从递归呼叫返回后，先开关方向（利用当前节点的堆栈上维护的信息），然后返回（通过）新头。线索是在堆栈上放置两个引用，以便可以为每个列表元素恢复链接方向。

reverselist.java

class ListElement {
    String name;
    ListElement next;
    ListElement(String name, ListElement next) {
        this.name = name;
        this.next = next;
    }
}

 public class ReverseList {
    static ListElement reverseList(ListElement previous, ListElement node) {
        if (node == null) { // reached end directly behind last node
            return previous; // new list head
        } else {
            ListElement newHead = reverseList(node, node.next);
            node.next = previous; // turn link direction
            return newHead; // pass through new list head
        }
    }

    static void printList(ListElement list) {
        while (list != null) {
            System.out.print(list.name + " -> ");
            list = list.next;
        }    
        System.out.println("null");
    }

    public static void main(String args[]) {
        ListElement c = new ListElement("c", null);
        ListElement b = new ListElement("b", c);
        ListElement a = new ListElement("a", b);

        ListElement head = a;
        printList(head);
        head = reverseList(null, head); // new list end and head of list
        printList(head);
    }
}

让我们看看我们得到的是：

$ javac ReverseList.java
$ java ReverseList      
a -> b -> c -> null
c -> b -> a -> null
$  

在逐步下降时也可以转动链接方向：

        else {
            ListElement tmp = node.next;
            node.next = previous; // turn link direction
            return reverseList(node, tmp); // pass through new list head
        }

但是，我更喜欢在修改列表之前先先到达末端（底部）。在堆栈溢出的情况下，这会防止断裂的链接。