对一段递归检查链接列表是否回文的代码感到好奇

Question

bool isPalindromeUtil(struct node **left, struct  node *right)
{
   /* stop recursion when right becomes NULL */
   if (right == NULL)
      return true;

   /* If sub-list is not palindrome then no need to
       check for current left and right, return false */
   bool isp = isPalindromeUtil(left, right->next);
   if (isp == false)
      return false;

   /* Check values at current left and right */
   bool isp1 = (right->data == (*left)->data);

   /* Move left to next node */
   *left = (*left)->next;

   return isp1;
}

// A wrapper over isPalindromeUtil()
bool isPalindrome(struct node *head)
{
   isPalindromeUtil(&head, head);
}

看，当链表中包含奇数时，当左指针和右指针在链表的中间相遇时。对于节点，如果左右指针之间的交叉已经发生，我们是否可以通过设置一个等于 true 的标志来更快地终止循环，然后如果标志为真，我们可以直接返回 true 而无需遍历所有那些案例检查？？

@m ohem，我的问题是我们是否可以在指针交叉时通过将全局标志设置为 true 来缩短指针交叉时返回 true 的过程。使用您建议的 jmp 操作

Answer 1

你的函数是递归的。它首先递归到列表的末尾，这样 left 位于列表的头部，right 位于列表的尾部。当它从递归返回时，它会进行实际的回文检查。 right 的值随着 recursin 展开而向后走，而 left 向前走。这必须通过指针引用发生，以便递归函数的其他实例看到更改。

递归为 right 的先前值提供了一个堆栈，因为单向链表不能在不跟踪它去过的地方的情况下向后走。

现在谈谈你的问题。你基本上是对的:检查字母两次没有意义。但是递归一直向上；它也必须一直下降。一旦其中一个测试为假，它就可以使测试短路(尽管它仍然必须向下传递 false 值，直到达到 isPalindrome)，但是如果单词是回文，所有内容都检查两次。

如果您觉得大胆，可以尝试使用 longjmp 和 setjmp 跳出递归，但您可能不希望这样。你想要的是一个双向链表，你可以在一个循环中以相反的方向遍历它。如果你的两个指针交叉，就跳出循环。