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

问题描述

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

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 语句中返回 False？这样就好了，不是吗？因为它只是意味着我们已经到达链表的末尾，还是我读错了？

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

那么我们只是简单地将最初指向链表头部的front_pointer移动到下一个要检查的节点？但是，虽然我理解这一点，但从后端，我们如何从最后一个节点移动到倒数第二个节点？

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

标签： pythonlinked-listpalindrome

解决方案

语句之后if head：为什么我们要返回False第一个 if 语句，什么时候recursively_check(head.next)指向None？这样就好了，不是吗？因为它只是意味着我们已经到达链表的末尾，还是我读错了？

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

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

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

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

那么我们只是简单地将front_pointer最初指向链表头部的 , 移动到下一个要检查的节点？

是的

但是，虽然我理解这一点，但从后端，我们如何从最后一个节点移动到倒数第二个节点？

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

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

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

我们立即达成此声明。当我们到达那里时，它上面的函数还没有执行。正是这条语句将启动递归，我们需要从该调用中获取信息，而该信息就是我们想要返回的信息。

这是的唯一return声明isPalindrome。其他return语句recursively_check仅服务。他们不执行退货isPalindrome。

每次我们退出嵌套执行时，recursively_check我们都会多测试一对节点。如果我们发现价值差异，我们开始返回False。如上所述，False从那时起，这将成为所有未完成调用的返回值recursively_check，包括直接在中进行的调用isPalindrome。

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

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

问题描述

解决方案

推荐阅读