# You should not change the original structure of LinkedList. So use Recurssion

• ``````class Solution {
public:
bool isPalindrome_internal(ListNode *p, ListNode **q, int len) {

//base case
if (p->next == *q || ((len % 2) && p->next->next == *q)) {
if (p->val == (*q)->val) {
*q = (*q)->next; //if base case is palindrome, adjust q to q->next, p will become p->prev when sub call returned
return true;
}
return false;
}
// recursively test if sub link is palindrome
bool sub_valid =  isPalindrome_internal(p->next, q, len);
if (!sub_valid) return false;

//sub link is valid, added front and end are equal
if (p->val == (*q)->val) {
*q = (*q)->next;
return true;
}
return false;
}

bool isPalindrome(ListNode* head) {

//count the length of linked-list
ListNode *p = head;
int len = 1;
while (p->next) {
len++;
p = p->next;
}
if (len <= 1) return true;

//initial q to point to the mid node+1 eg: 1 2 1 q=1. 1 2 2 1 q = 2. 1 2 3 4 1 q = 4.
ListNode *q = head;
for (int i = 0; i < (len+1)/2; i++) q = q->next;

return isPalindrome_internal(head, &q, len);
}
};``````

• but recursion needs o(n) space

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.