C++:正在检查LinkedList中的回文-递归方法-错误

Question

我试图通过递归地向下到列表中的最后一个节点并比较列表中的第一个节点和最后一个结点来在给定的链表中找到回文。

我的LinkedList有一个带有int值成员和指向下一个节点的指针的标准节点。

我将一个指向head节点指针的指针作为第一个参数，并在每次成功匹配时将其更改为下一个参数，但我在语法中遇到了错误。有人能解释一下我为什么会出现这个错误吗？

代码片段：

bool isPalindromeRecur(Node** left, Node* right){
if(right == nullptr) return true;
bool isP = isPalindromeRecur(left,right->next);
if(!isP) return false;
bool isP1 = (*(left)->val == right->val);
*left = *(left)->next;
return isP1;
}

我在第5行和第6行出现错误。

error: request for member 'val' in '* left', which is of pointer type 'Node*' (maybe you meant to use '->' ?)
bool isP1 = (*(left)->val == right->val);
^~~
error: request for member 'next' in '* left', which is of pointer type 'Node*' (maybe you meant to use '->' ?)
*left = *(left)->next;
^~~~

Answer 1

您应该在两行中使用(*left)->...而不是*(left)->...。->运算符比*运算符具有更高的偏好，因此*(left)->next将被解析为*(left->next)。由于left的类型是Node **，这将类似于尝试访问指针的next成员。

Answer 2

递归调用应处于所有必需条件下。您的第一个条件是错误的，并且不够强，无法通过递归调用进行休耕。

另外，第一个参数Node** left类型是一个过度使用。当您需要修改列表(插入或删除项(时，这种参数非常有用。

bool isPalindromeRecur(Node* left, Node* right) {
assert(left);
assert(right);
if (left == right) return true; // for odd length
if (left->value != right->value) return false;
if (left->next == right) return true; // for even length
return isPalindromeRecur(left->next, right->prev);
}

如果你的列表不是双重链接的，那么这就更难做到。