Error when changing the order of A and B in (A&B) AND operator

Question

Below is the code to find whether a LinkedList is a palindrome or not Why this code show error for when this line bool isPal = check(p->next) & (temp->val == p->val); in the code below is written as bool isPal = (temp->val == p->val) & check(p->next); for the input [1,0,1]-------just the order of taking AND is reversed

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;
    }
};

Answer 1

Solution

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

This fixes the issue by deliberately moving the call to check() to be first so that temp can be iterated inside of the check() call before trying to calculate the value of temp.

---

Explanation

consider the following:

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

The value of temp is calculated Before the call to check() and thus before temp can ever be iterated.

Step-By-Step Walkthrough

Using the [1,0,1] example, I will step through the recursive calls of check() step-by-step:

• call to isPalindrome() happens => temp is set to head then the recursive check function is called.
• 1st call to check() =>
  • p is the 1st list element.
  • temp is 1st list element.
  • (temp->val == p->val) is calculated as true because they are the same element. Then check(p->next) is called.
• 2nd call to check() =>
  • p is the 2nd list element.
  • temp is 1st list element.
  • (temp->val == p->val) is calculated as false because 1 != 0. Then check(p->next) is called. the call is not skipped because we are using the & operator not the && operator.
• 3rd call to check() =>
  • p is the 3rd list element.
  • temp is 1st list element.
  • (temp->val == p->val) is calculated as true because 1 == 1. Then check(p->next) is called, but p-> next is NULL because we are at the end of the list.
• 4th call to check() =>
  • p is NULL.
  • temp is 1st list element.
  • returns true immediately. 3rd check() call can now continue.
• 3rd call to check() (cont.) =>
  • isPal is set as true (1 & 1 == 1).
  • temp set as 2nd list element.
  • returns true. 2nd check() call can now continue.
• 2nd call to check() (cont.) =>
  • isPal is set as false (0 & 1 == 0).
  • temp set as 3rd list element.
  • returns false. 1st check() call can now continue.
• 1st call to check() (cont.) =>
  • isPal is set as false (1 & 0 == 0).
  • temp set as 3rd list element.
  • returns false.