#### Basic idea.

Getting O(n) in time is trivial. The problem with space complexity of this problem is that when checking the i-th list, we need to compare with the (N-i)-th list, which can't be naively accessed in O(1) time. Inspired by the solution for Implement Queue using stacks , we can achieve O(1) space (not including function stack) in a similar fashion.

*The main point is, while traversing to the (N-i)-th list, we also check the lists along the path.*

#### Implementation detail

We need to return have two things from the recursion:

- pointer to (N-i)-th list
- whether the sublists in between form a palindrome.

Instead of creating a new class, I simply used the given ListNode structure, where:

- val is value of (N-i)-th list, but if the sublists in between is not palindrome, this value will be set to val[i] + 1 so that comparing val[i] and val is never true;
- next pointer to (N-i)-th list

We only need to create one ListNode which will be propagated through the recursion. Hence the extra space is O(1). Of course, if counting the space used for recursion stack, it's still O(n).

#### Code

Below is my 19ms accepted answer.

```
class Solution {
private:
ListNode* helper(ListNode* head,int n)
/*head: pointer at i-th list
n: lists length
node->val: val[i+n] or val[i]+1
node->next: pointer to (i+n)-th list
*/
if (n==1) {
ListNode* node = new ListNode(head->val);
node->next=head;
return node;
}
if (n==2) {
ListNode* node = new ListNode(head->next->val);
node->next = head->next;
return node;
}
//recursion on (i+1) and (n-i-1)
ListNode* node = helper(head->next, i-2);
node->next = node->next->next; // points to (n-i)th list
//only return val[n-i] if sublists form palindrome.
if (head->next->val != node->val) node->val = head->val+1;
//otherwise return val[i]+1 for false comparison result
else node->val = node->next->val;
return node;
}
public:
bool isPalindrome(ListNode* head) {
int n=0;
ListNode* node=head;
while(node) {
n++;
node=node->next;
}
if(!n) return true;
node = helper(head,n);
int val = node->val;
delete node;
return head->val == val;
}
};
```