0

下面是查找 LinkedList 是否为回文的代码 为什么此代码在此行时显示错误 bool isPal = check(p->next) & (temp->val == p->val); 在下面的代码中写为 bool isPal = (temp->val == p->val) & check(p->next); 对于输入[1,0,1]-------只是取AND的顺序相反

class Solution {
public:
       ListNode* temp;
       bool isPalindrome(ListNode* head) {
           temp = head;
           return check(head);
    }
    
       bool check(ListNode* p) {
           if (NULL == p) return true;
           bool isPal = check(p->next) & (temp->val == p->val);
           temp = temp->next;
           return isPal;
    }
};
4

1 回答 1

0

解决方案

bool a = check(p->next);
bool b = (temp->val == p->val);
bool isPal = a & b;

这通过故意将调用 check() 移动到第一个来解决问题，以便在尝试计算 temp 的值之前可以在 check() 调用内部迭代 temp。

解释

考虑以下：

bool b = (temp->val == p->val);
bool a = check(p->next);
bool isPal = a & b;

temp 的值是在调用 check() 之前计算的，因此在 temp 可以迭代之前。

分步演练

使用 [1,0,1] 示例，我将逐步执行 check() 的递归调用：

  • 调用 isPalindrome() 发生 => temp 设置为 head 然后调用递归检查函数。
  • 第一次调用 check() =>
    • p 是第一个列表元素。
    • temp 是第一个列表元素。
    • (temp->val == p->val) 计算为真，因为它们是相同的元素。然后调用 check(p->next)。
  • 第二次调用 check() =>
    • p 是第二个列表元素。
    • temp 是第一个列表元素。
    • (temp->val == p->val) 被计算为假，因为 1 != 0。然后调用 check(p->next)。调用不会被跳过，因为我们使用的是 & 运算符而不是 && 运算符。
  • 第三次调用 check() =>
    • p 是第三个列表元素。
    • temp 是第一个列表元素。
    • (temp->val == p->val) 计算为真，因为 1 == 1。然后调用 check(p->next)，但 p->next 为 NULL，因为我们位于列表的末尾。
  • 第四次调用 check() =>
    • p 为 NULL。
    • temp 是第一个列表元素。
    • 立即返回真。第三个 check() 调用现在可以继续。
  • 第三次调用 check()（续）=>
    • isPal 设置为真 (1 & 1 == 1)。
    • temp 设置为第二个列表元素。
    • 返回真。第二个 check() 调用现在可以继续。
  • 第二次调用 check()（续）=>
    • isPal 设置为假 (0 & 1 == 0)。
    • temp 设置为第三个列表元素。
    • 返回假。第一次 check() 调用现在可以继续。
  • 第一次调用 check()（续）=>
    • isPal 设置为假 (1 & 0 == 0)。
    • temp 设置为第三个列表元素。
    • 返回假。
于 2020-09-03T21:01:01.113 回答