使用递归检查回文时，后向指针如何移动？

Question

我找到了一个检查链表是否回文的递归解决方案：

def isPalindrome(self, head: ListNode) -> bool:

    self.front_pointer = head

    def recursively_check(head):
        if head:
            if not recursively_check(head.next):
                return False
            if self.front_pointer.val != head.val:
                return False
            self.front_pointer = self.front_pointer.next
        return True

    return recursively_check(head)

'if head'语句后：

当“recursively_check(head.next)”指向 None 时，为什么第一个 if 语句 return 为 False？这没关系，不是吗？因为它只是意味着我们已经到达链表的末尾，还是我读错了？

对于第二个 if 语句，这种是有道理的——在我看来它是在检查第一个节点 front_pointer 和最后一个节点 head 是否相同？

那我们就是简单的把最初指向链表头的front_pointer移动到下一个节点去查？但是虽然我理解这一点，但从后端来看，我们如何从最后一个节点移动到倒数第二个节点？

最后，我们为什么return递归调用recursively_check()？我不知道我们什么时候会到达这个代码 - 因为我们到达这里时我们会 returned True 或 False，不是吗？

Answer 1

After the if head statement: Why are we returning False for the first if statement, when recursively_check(head.next) points to None? This would be okay, no? Because it simply means we've reached the end of the linked list, or am I reading this wrongly?

recursively_check(head.next) 不“指向 None”。它是一个布尔值：要么是 True，要么是 False。将 True 解释为“到目前为止它看起来像回文”并将 False 解释为“这绝对不是回文”。

这个特定的 return False 旨在通过在递归调用树中检测到更深的故障来退出递归。在这里，我们只是将该消息传递给调用者，调用者也会这样做。它与到达列表末尾无关。它是由递归树中更深层次的差异触发的。

For the second if statement, this kind of makes sense- in my mind it is checking the first node front_pointer and the last node head are the same?

是的，第一次执行就是这样

Then we are simply moving the front_pointer, which initially points to the head of the linked list to the next node to check?

是

But while I understand this, from the back end, how are we moving from the last node to the second last node?

这是通过递归处理的。每个递归调用都会得到它自己的 head 变量。当我们用 head.next 初始化它时，更深递归调用将在列表中 进一步 初始化它们的 head 。

这意味着当我们回溯超出递归级别时，我们进入一个执行上下文，其 head 变量设置为 previous 节点比更深层调用正在使用的节点（正如我们给它 head.next）。因此，仅通过 return 退出当前执行上下文，我们就会回退到先前的值 head，这相当于在列表中后退一步。但是请注意，这里的 head 变量与列表中的节点一样多。在递归调用堆栈中，它们全部堆叠在一起。通过展开调用堆栈，我们可以使用之前的 head 变量。

Finally, why do we return the recursive call recursively_check()? I don't see when we will reach this code- as we would have returned True or False by the time we reach here, no?

我们立即得出这个声明。当我们到达那里时，它上面的功能尚未执行。正是这条语句将开始递归，我们需要从那个调用中获取信息，而这些信息就是我们想要的 return.

这是 isPalindrome 的唯一 return 声明。其他 return 语句仅用于 recursively_check。他们不会为 isPalindrome.

执行 return

每次我们退出 recursively_check 的嵌套执行时，我们都测试了一对节点。如果我们发现值有差异，我们将开始 returning False。如上所述，此 False 从那时起将成为 recursively_check 的所有未完成调用的 return 值，包括直接在 isPalindrome.[=51 中进行的调用=]

另一方面，只要比较相等，每个嵌套的 recursively_check 调用都会 return 编辑 True。如果事实证明比较总是相等，那么 isPalindrome 对 recursively_check 的调用也会得到 True 返回。

使用递归检查回文时，后向指针如何移动？

How does the back pointer move when using recursion to check a palindrome?

python

linked-list

palindrome