英文:
How does this recursion and back tracking work in LeetCode?
问题
这个函数会倒序打印链表的节点：
void recur(ListNode head) {
if (head == null) return;
recur(head.next);
tmp.add(head.val);
}
如果链表是 1 -> 2 -> 3，那么 tmp（一个 ArrayList）会添加节点的值。
最后，通过打印 tmp，我们可以得到一个列表 [3, 2, 1]。然而，我不知道为什么它能够正常工作。为什么 recur 函数会循环到最后一个节点，然后倒序添加值呢？
英文:
This function which will print the nodes of a linked list in reverse:
void recur(ListNode head) {
if(head == null) return;
recur(head.next);
tmp.add(head.val);
}
If the list is 1 -> 2 -> 3 then tmp (an ArrayList) will add the value of the node.
At last, we can get a list [3, 2, 1] via printing tmp. However, I do not know why it works. Why does the recur function loop to the last node then add the values in reverse order?
答案1
得分: 1
我认为这个流程图可能对你有所帮助。
如图所示，当链表末尾被达到时，head.value 被添加到 tmp 列表中。也就是说，head 变为 null。
英文:
I think this flow diagram may help you.
As you can see from the diagram the head.value is added to the tmp list only when end of the linked list is reached. i.e . head becames null
答案2
得分: 0
代码部分已翻译完成，如下所示：
void recur(ListNode head) {
if (head == null) return;
tmp.add(head.val);
}
- 在第一步中，头部指向值为
1，这个条件检查if (head == null)将返回false，因为头部节点不是空的。 - 然后我们调用相同的函数
recur，但是针对值为2的下一个节点，执行recur重新开始，但是以节点2作为头部节点。我们再次检查if (head == null)->false，同样的原因，这里头部不是空的。 - 然后我们调用相同的函数
recur，但是针对下一个节点，这个节点是空的head.next -> null，因为在节点2之后没有节点了。我们检查if (head == null)，但是现在我们有了true，表示当前节点，意味着没有节点留在后面，我们不能继续调用recur()。因此，我们用return语句停止递归。 - 现在，我们再次返回到步骤＃2并继续执行，因为
recur(head.next)的执行通过return语句结束。这意味着，这个节点是最后一个节点，我们将其值放入tmp。并且recur对于 ListNode2的执行结束了，因为在此之后没有代码行了。 - 现在，我们再次返回到步骤＃1，并按照步骤4中描述的相同逻辑进行。由于节点
2的recur执行结束，我们继续执行并将值1放入tmp数组中。
if (head == null) - 这个检查被称为递归的“基本情况”，意思是“何时需要结束执行并退出？”如果没有它，递归将无限地进行下去。
我们深入到 ListNode 的末尾，然后再次返回到顶部。
为了能够将 ListNode 的值放入 tmp 中，我们首先需要将下一个值放入 tmp，依此类推。
我希望我解释得更准确，现在对您更加清晰。
英文:
It's pretty much simple, let's consider the [1 -> 2] node with two ListNode and we want to reverse with you function:
void recur(ListNode head) {
if (head == null) return;
recur(head.next);
tmp.add(head.val);
}
- On the first stem, the head will point to
1value, this checkif (head == null)will returnfalsesince head node is not null. - Then we call the same function
recurbut for the next node with value2, and execution ofrecurstart over but with node2as a head node. We again checkif (head == null)->false, same reason, head is not null here. - Then we call the same function
recurbut for the next node which is nullhead.next -> null, since there are no nodes anymore after node2. We checkif (head == null), but now we havetrue, the current node, meaning there are no nodes left after and we can't go further callingrecur()again. So, we stop the recursion with areturnstatement. - Now, we return again to step #2 and continue execution, because the execution of
recur(head.next)ends byreturnstatement. That means, this node is the last one, and we put its value to thetmp. And the execution ofrecurfor ListNode2ends, since there are no code lines after. - Now, we return again to step #1 and do the same logic as described in step 4. Since
recurfor node2ends its execution we proceed and put value1totmparray.
if (head == null) return; - this check, called recursion base case, meaning when we need to end execution and exit?, without it recursion will go infinitely.
We dig to the end of the ListNode and then return again to the top.
To be able to put ListNode value to the tmp we need first put next value to the tmp and so on.
I hope, I explained more accurately and its more clear for you now.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论