Given a singly linked list, determine if it is a palindrome.

Example 1:

``````Input: 1->2
Output: false
``````

Example 2:

``````Input: 1->2->2->1
Output: true
``````

Could you do it in O(n) time and O(1) space?

``````class Solution {
public:
stack<int> st;
while (cur) {
st.push(cur->val);
cur = cur->next;
}
int t = st.top(); st.pop();
if (head->val != t) return false;
}
return true;
}
};
``````

``````class Solution {
public:
}
bool helper(ListNode* node, ListNode*& cur) {
if (!node) return true;
bool res = helper(node->next, cur) && (cur->val == node->val);
cur = cur->next;
return res;
}
};
``````

``````class Solution {
public:
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
st.push(slow->val);
}
if (!fast->next) st.pop();
while (slow->next) {
slow = slow->next;
int tmp = st.top(); st.pop();
if (tmp != slow->val) return false;
}
return true;
}
};
``````

``````class Solution {
public:
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *last = slow->next, *pre = head;
while (last->next) {
ListNode *tmp = last->next;
last->next = tmp->next;
tmp->next = slow->next;
slow->next = tmp;
}
while (slow->next) {
slow = slow->next;
if (pre->val != slow->val) return false;
pre = pre->next;
}
return true;
}
};
``````

Githbu 同步地址：

https://github.com/grandyang/leetcode/issues/234

Palindrome Number

Validate Palindrome

Palindrome Partitioning

Palindrome Partitioning II

Longest Palindromic Substring