题目
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
Follow up:
Could you do it in O(n) time and O(1) space?
解析
之前做过字符串的回文判断，相对比较简单，只需要前后对比即可。现在对于链表来说，前后来判断，直接做的话是没有办法的。
题目中要求使用O(n)的时间和O(1)的空间，即遍历一遍或者有限次遍就可以完成。所以，
（1）首先找到列表的中间结点；
（2）后半链表逆序；
（3）前后进行判断是否为回文。
中间结点，如果为奇数的话则后半链表比前半少一个节点，偶数则相同。寻找中间节点的办法可以使用快慢指针，快指针走两步，慢指针走一步，走到最后，慢指针的位置便为中间节点的位置。
代码（C语言）
bool isPalindrome(struct ListNode* head) {
if (!head || !(head->next))
return true;
// use fast & slow pointer to find middle of list
struct ListNode* fastP = head, * slowP = head;
while (fastP->next && fastP->next->next) {
fastP = fastP->next->next;
slowP = slowP->next;
}
struct ListNode* secHalfHead = slowP->next;
slowP->next = NULL;
// reverse second half list
struct ListNode* p1 = secHalfHead, * p2 = secHalfHead->next;
while (p1 && p2) {
struct ListNode* tmpNode = p2->next;
p2->next = p1;
p1 = p2;
p2 = tmpNode;
}
secHalfHead->next = NULL;
struct ListNode* p = p2 ? p2 : p1;
struct ListNode* q = head;
while (p) {
if (p->val != q->val)
return false;
p = p->next;
q = q->next;
}
return true;
}
