所以，我在java中學習DSA并開始反轉鏈表。我了解迭代方法，但是在學習遞回方法時，有一個時間點遞回做了兩件事：
- 反轉鏈接
- 遍歷到串列底部并確定新的頭部
Q1。哪個先出現？（請一步一步地）堆疊遍歷到底部，在向上的程序中反轉鏈接并回傳新的頭部或鏈接在底部反轉并且到達時將新的頭部回傳到最佳。
Q2。新節點如何回傳到它上面的遞回（請一步一步）？
如果我理解錯了，有人可以向我解釋一下遞回是如何深入作業的嗎？不只是通過陳述將其留給遞回的信念飛躍。我想深入了解它及其步驟。
uj5u.com熱心網友回復：
Q1：遍歷鏈表到最后，在堆疊上保留反向鏈接，將新的頭回傳到頂部。（另一種方式也可以在輸出后面看到。）
Q2：想法總是退回新的頭部，而不是立即退回。從遞回呼叫回傳后，首先切換方向（利用當前節點的堆疊上維護的資訊），然后回傳（通過）新的頭。線索是將兩個參考放在堆疊上，以便可以為每個串列元素恢復鏈接方向。
反向串列.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
}
不過，我更喜歡在修改串列之前先到達末尾（底部）。這可以防止在堆疊溢位的情況下斷開鏈接。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/487720.html