这个带递归的链表反转如何工作？
How can this linked list reversal with recursion work?
我正在看这个反转给定链表的函数的递归实现：
static Node reverse(Node head) {
if(head == null) {
return head;
}
// last node or only one node
if(head.next == null) {
return head;
}
Node newHeadNode = reverse(head.next);
// change references for middle chain
head.next.next = head;
head.next = null;
// send back new head node in every recursion
return newHeadNode;
}
public static void main(String[] args) throws IOException {
LinkedList llist = new LinkedList();
llist.insertNode(20);
llist.insertNode(4);
llist.insertNode(15);
llist.insertNode(85);
Node llistReversed = reverse(llist.head);
printSinglyLinkedList(llistReversed, " ");
}
所以链表节点为：85 15 4 20
我以为调用reverse后head.next会指向第二个值为15的节点？如果是这样，这段代码如何（递归地）反转这个链表？
对于一个普通的单链表，是的，head.next指向或指的是包含15的结点。在递归方法的第一次调用中，即。在下一次调用中它将是 4，然后是 20。
看第一次调用（head.next指向15）reverse(head.next) returns将15 4 20反转为20 4 15后的新头，即指针或引用20个节点。
该方法的工作原理：递归调用后，15 节点指向 85 节点，85 节点指向空。请注意，我们在这些操作中仍然使用旧的 head。这确保 85 附加在 20 4 15 之后，因此完成反向操作。最后返回我们从递归调用中得到的新头，即对 20 的引用。
两个建议：画在纸上。并且 运行 它在你的调试器中。
如果能看到包括 reverse 的方法签名在内的完整代码会有所帮助，但我假设 head 实际上不是整个列表的头部，而是部分列表的头部递归调用反向时传递的列表
因此，除了用于在到达列表末尾时停止递归的空检查之外，因为递归方法所做的第一件事是调用自身传递列表中它有效移动的下一个节点一直到列表的末尾然后随着堆栈的展开开始返回
因此，该方法的每次迭代都会建立对 head 的引用，该 head 是列表中的特定节点，并且尚未修改其下一个节点。通过使自己成为下一个之后的下一个，它会将自己移动到列表的末尾，但可能更容易想象 link 的方向是相反的：
A>B>C>D
如果我们一路旅行到 D 然后返回一个（因为 D 的下一个为空）所以我们在 C，通过使 C 的下一个（D）的下一个等于 C 我们将 D 指向 C这有助于将 linkC 和 D 之间的年龄
A>B>C><D
C 仍然指向 D，但现在 D 指向 C
然后我们做 head.next = null 停止 C 指向 D..
null
ᐱ
A>B>C<D
..但这通常是无意义的操作，因为它即将被再次覆盖..
..当我们退回到B并使B的nextnext指向B时，这是一种说“使C的下一个指向B”的方式
A>B><C<D
我们刚刚将 C 指向 null 是没有实际意义的，因为我们只是将 C 指向 B，但它在一种情况下确实有用..
.. 最终我们将到达 A，将 A 的下一个 (B) 指向 A，然后将 A 的下一个 (B) 设置为 null，我们确实需要这样做，因为没有什么需要处理的了。如果我们不在 A 的下一个上设置 null，我们将来永远无法到达列表的末尾，因为它循环（B 指向 A 指向 B 指向 A 等）
null
ᐱ
A<B<C<D
我们的名单颠倒了
最后要注意的是，在压缩到列表的末尾之后，我们有效地将 D 一直作为新的 HeadNode 和 return 携带回来，以便它可以将其捕获为新的头部（否则我们会无法访问除 A)
之外的所有列表
要查看其是否正常工作，请从只有一个节点的列表开始。很明显，在这种情况下，节点是 return 通过以下 if 语句按原样编辑的：
if (head.next == null) {
return head;
}
这确实是您所期望的：具有一个节点的列表的反转不应该对该列表进行任何更改；头应该引用同一个节点。
感应
我们现在可以继续分析 2 个节点、3 个节点、4 个节点、5 个节点等的算法。但我们可以在这里使用归纳证明：
假设我们有一个任意大小大于 1 的列表，如下所示：
head
↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 85 │ │ value: 15 │ │ value: 20 │
│ next: ———————→ │ next: ———————→ ...more nodes...——→ │ next:null │
└───────────┘ └───────────┘ └───────────┘
然后我们将执行：
Node newHeadNode = reverse(head.next);
head->next 是对第二个节点（值为 15 的节点）的引用。此引用传递给 reverse.
的递归调用
现在 reverse 的每次执行都有自己的执行上下文，在更深层次的上下文中，我们获得了 head 变量的新实例。它使用作为参数传递的值进行初始化。所以在这种情况下 that head 指的是值为 15.
的节点
对于 reverse 的这个递归执行上下文，这是列表的 first 节点（因为它不知道带有 85 的节点），它的自己的 head 变量引用了它：
head
↓
┌───────────┐ ┌───────────┐
│ value: 15 │ │ value: 20 │
│ next: ———————→ ...more nodes...——→ │ next:null │
└───────────┘ └───────────┘
我们现在将假设这个调用将正确地反转那个更短的列表并将return旧尾节点，已成为新头节点（值为20）：
head (returned)
↓ ↓
┌───────────┐ ┌───────────┐
│ value: 15 │ │ value: 20 │
│ next:null │ ←——...more nodes... ←——————— :next │
└───────────┘ └───────────┘
执行return，更深层次的执行上下文消失，returned引用赋值给outer执行上下文中的newHeadNode ，其中 head 仍然指代值为 85 的节点：
head newHeadNode
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 85 │ │ value: 15 │ │ value: 20 │
│ next: ———————→ │ next:null │ ←——...more nodes... ←——————— :next │
└───────────┘ └───────────┘ └───────────┘
请注意我们如何假设：
- 该较短列表中的所有链接现在有效地指向“另一条路”；
- 跟在
head之后的节点已成为尾节点，其next 属性设置为null；
- 新头是前一个尾节点，并且对它的引用是return由递归函数调用编辑的。
然后执行：
head.next.next = head;
这反映在这里：
head newHeadNode
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 85 │ │ value: 15 │ │ value: 20 │
│ next: ———————→ │ │ │ │
│ │ ←——————— :next │ ←——...more nodes... ←——————— :next │
└───────────┘ └───────────┘ └───────────┘
并且：
head.next = null;
这是有道理的，因为如果列表被颠倒了，那么头部现在就是尾部，尾部节点后面应该没有其他节点了：
head newHeadNode
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 85 │ │ value: 15 │ │ value: 20 │
│ next: null│ ←——————— :next │ ←——...more nodes... ←——————— :next │
└───────────┘ └───────────┘ └───────────┘
最后：
return newHeadNode;
所以...我们看到如果我们的假设是正确的，那么我们就正确地反转了列表。
当我们验证它适用于具有 1 个节点的列表时，我们现在还发现如果它适用于大小为 1 的列表，它也适用于大小为 +1 的列表，我们有证据证明它适用于任何列表。
如何head“移动”
您可以想象变量 head 将如何在每次更深的递归调用时“行走”到下一个节点，直到它到达列表中的最后一个节点。然后基本情况开始，不再发生递归。随着执行从递归中回溯，head 似乎以相反的方向返回到它开始的位置。
虽然这样看会有所帮助，但这并不完全正确：reverse 的每个执行上下文都有自己的 head 版本，实际上永远不会移动。它是一个恒定的参考。然而，由于每个递归调用都将 head->next 作为参数，存在于更深层执行上下文中的新 head 变量将使用该 next 节点进行初始化。因此 reverse 的每个单独执行上下文都有一个 head 变量引用 不同的 节点。每当 reverse 的一次调用执行结束时，执行将返回到先前的执行上下文，在那里我们再次处理一个变量 head ，它没有移动并且仍然引用与之前相同的节点递归调用之前的情况。
我正在看这个反转给定链表的函数的递归实现：
static Node reverse(Node head) {
if(head == null) {
return head;
}
// last node or only one node
if(head.next == null) {
return head;
}
Node newHeadNode = reverse(head.next);
// change references for middle chain
head.next.next = head;
head.next = null;
// send back new head node in every recursion
return newHeadNode;
}
public static void main(String[] args) throws IOException {
LinkedList llist = new LinkedList();
llist.insertNode(20);
llist.insertNode(4);
llist.insertNode(15);
llist.insertNode(85);
Node llistReversed = reverse(llist.head);
printSinglyLinkedList(llistReversed, " ");
}
所以链表节点为：85 15 4 20
我以为调用reverse后head.next会指向第二个值为15的节点？如果是这样，这段代码如何（递归地）反转这个链表？
对于一个普通的单链表，是的，head.next指向或指的是包含15的结点。在递归方法的第一次调用中，即。在下一次调用中它将是 4，然后是 20。
看第一次调用（head.next指向15）reverse(head.next) returns将15 4 20反转为20 4 15后的新头，即指针或引用20个节点。
该方法的工作原理：递归调用后，15 节点指向 85 节点，85 节点指向空。请注意，我们在这些操作中仍然使用旧的 head。这确保 85 附加在 20 4 15 之后，因此完成反向操作。最后返回我们从递归调用中得到的新头，即对 20 的引用。
两个建议：画在纸上。并且 运行 它在你的调试器中。
如果能看到包括 reverse 的方法签名在内的完整代码会有所帮助，但我假设 head 实际上不是整个列表的头部，而是部分列表的头部递归调用反向时传递的列表
因此，除了用于在到达列表末尾时停止递归的空检查之外，因为递归方法所做的第一件事是调用自身传递列表中它有效移动的下一个节点一直到列表的末尾然后随着堆栈的展开开始返回
因此，该方法的每次迭代都会建立对 head 的引用，该 head 是列表中的特定节点，并且尚未修改其下一个节点。通过使自己成为下一个之后的下一个，它会将自己移动到列表的末尾，但可能更容易想象 link 的方向是相反的：
A>B>C>D
如果我们一路旅行到 D 然后返回一个（因为 D 的下一个为空）所以我们在 C，通过使 C 的下一个（D）的下一个等于 C 我们将 D 指向 C这有助于将 linkC 和 D 之间的年龄
A>B>C><D
C 仍然指向 D，但现在 D 指向 C
然后我们做 head.next = null 停止 C 指向 D..
null
ᐱ
A>B>C<D
..但这通常是无意义的操作，因为它即将被再次覆盖..
..当我们退回到B并使B的nextnext指向B时，这是一种说“使C的下一个指向B”的方式
A>B><C<D
我们刚刚将 C 指向 null 是没有实际意义的，因为我们只是将 C 指向 B，但它在一种情况下确实有用..
.. 最终我们将到达 A，将 A 的下一个 (B) 指向 A，然后将 A 的下一个 (B) 设置为 null，我们确实需要这样做，因为没有什么需要处理的了。如果我们不在 A 的下一个上设置 null，我们将来永远无法到达列表的末尾，因为它循环（B 指向 A 指向 B 指向 A 等）
null
ᐱ
A<B<C<D
我们的名单颠倒了
最后要注意的是，在压缩到列表的末尾之后，我们有效地将 D 一直作为新的 HeadNode 和 return 携带回来，以便它可以将其捕获为新的头部（否则我们会无法访问除 A)
之外的所有列表要查看其是否正常工作，请从只有一个节点的列表开始。很明显，在这种情况下，节点是 return 通过以下 if 语句按原样编辑的：
if (head.next == null) {
return head;
}
这确实是您所期望的：具有一个节点的列表的反转不应该对该列表进行任何更改；头应该引用同一个节点。
感应
我们现在可以继续分析 2 个节点、3 个节点、4 个节点、5 个节点等的算法。但我们可以在这里使用归纳证明：
假设我们有一个任意大小大于 1 的列表，如下所示：
head
↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 85 │ │ value: 15 │ │ value: 20 │
│ next: ———————→ │ next: ———————→ ...more nodes...——→ │ next:null │
└───────────┘ └───────────┘ └───────────┘
然后我们将执行：
Node newHeadNode = reverse(head.next);
head->next 是对第二个节点（值为 15 的节点）的引用。此引用传递给 reverse.
现在 reverse 的每次执行都有自己的执行上下文，在更深层次的上下文中，我们获得了 head 变量的新实例。它使用作为参数传递的值进行初始化。所以在这种情况下 that head 指的是值为 15.
对于 reverse 的这个递归执行上下文，这是列表的 first 节点（因为它不知道带有 85 的节点），它的自己的 head 变量引用了它：
head
↓
┌───────────┐ ┌───────────┐
│ value: 15 │ │ value: 20 │
│ next: ———————→ ...more nodes...——→ │ next:null │
└───────────┘ └───────────┘
我们现在将假设这个调用将正确地反转那个更短的列表并将return旧尾节点，已成为新头节点（值为20）：
head (returned)
↓ ↓
┌───────────┐ ┌───────────┐
│ value: 15 │ │ value: 20 │
│ next:null │ ←——...more nodes... ←——————— :next │
└───────────┘ └───────────┘
执行return，更深层次的执行上下文消失，returned引用赋值给outer执行上下文中的newHeadNode ，其中 head 仍然指代值为 85 的节点：
head newHeadNode
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 85 │ │ value: 15 │ │ value: 20 │
│ next: ———————→ │ next:null │ ←——...more nodes... ←——————— :next │
└───────────┘ └───────────┘ └───────────┘
请注意我们如何假设：
- 该较短列表中的所有链接现在有效地指向“另一条路”；
- 跟在
head之后的节点已成为尾节点，其next属性设置为null； - 新头是前一个尾节点，并且对它的引用是return由递归函数调用编辑的。
然后执行：
head.next.next = head;
这反映在这里：
head newHeadNode
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 85 │ │ value: 15 │ │ value: 20 │
│ next: ———————→ │ │ │ │
│ │ ←——————— :next │ ←——...more nodes... ←——————— :next │
└───────────┘ └───────────┘ └───────────┘
并且：
head.next = null;
这是有道理的，因为如果列表被颠倒了，那么头部现在就是尾部，尾部节点后面应该没有其他节点了：
head newHeadNode
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 85 │ │ value: 15 │ │ value: 20 │
│ next: null│ ←——————— :next │ ←——...more nodes... ←——————— :next │
└───────────┘ └───────────┘ └───────────┘
最后：
return newHeadNode;
所以...我们看到如果我们的假设是正确的，那么我们就正确地反转了列表。
当我们验证它适用于具有 1 个节点的列表时，我们现在还发现如果它适用于大小为 1 的列表，它也适用于大小为 +1 的列表，我们有证据证明它适用于任何列表。
如何head“移动”
您可以想象变量 head 将如何在每次更深的递归调用时“行走”到下一个节点，直到它到达列表中的最后一个节点。然后基本情况开始，不再发生递归。随着执行从递归中回溯，head 似乎以相反的方向返回到它开始的位置。
虽然这样看会有所帮助，但这并不完全正确：reverse 的每个执行上下文都有自己的 head 版本，实际上永远不会移动。它是一个恒定的参考。然而，由于每个递归调用都将 head->next 作为参数，存在于更深层执行上下文中的新 head 变量将使用该 next 节点进行初始化。因此 reverse 的每个单独执行上下文都有一个 head 变量引用 不同的 节点。每当 reverse 的一次调用执行结束时，执行将返回到先前的执行上下文，在那里我们再次处理一个变量 head ，它没有移动并且仍然引用与之前相同的节点递归调用之前的情况。