/**
* Definition for singlylinked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
stack<int> s;
ListNode* tmp = head;
int count = 0;
while(tmp){
count++;
tmp = tmp>next;
}
if(count==1) return true;
int half = count/2 + count%2;
for(int i=1; i<=half;i++){
s.push(head>val);
head = head>next;
}
if(count%2) s.pop(); // incase of {1,0,0} such cases
while(head && head>val == s.top()){
head = head>next;
s.pop();
}
if(!head) return true;
return false;
}
};
C++ using stack, simple and easy understand.


I have similar idea about solution. Reverse second half, then compare. However, I got Time Limit Exceeded with input [1,0,0]. Any idea?
bool isPalindrome(struct ListNode* head) { if (head == NULL) return true; struct ListNode *p=head, *q, *r, *tail=head; int len = 1, i; while (tail>next != NULL) { len++; tail = tail>next; } for (i=0; i<len/2; i++){ p = p>next; } // now p is the start of second half q = p>next; while(q!=NULL){ r = q>next; q>next = p; p = q; q = r; } p = head; q = tail; for (i=0; i<len/2; i++){ if (p>val != q>val) return false; p = p>next; q= q>next; } return true;
}