题目
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
分析
判断一个链表是否为回文。
要求时间复杂度O(n) 空间复杂度O(1)
若是可用辅助空间，则其是一个简单的题目，我们可用利用一个辅助数组存储节点元素val值，然后判断数组是否回文即可。
题目要求O(1)的空间复杂度，不能用辅助空间。我们只能从链表本身下手，既然判断回文，需要将链表一分为二，判断两部分是否对称，由于为单向链表，采取反转其中一半链表，然后逐个对比。
如何将链表一分为二呢？采用快行指针的方法，设置slow和fast，slow每行一步，fast行走两步，当fast走到链表末尾，slow则恰好走到中间。（注意处理链表长度为奇数的情况）
然后采用头插法将后半部分链表反转，再与前半部分对比。
AC代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == NULL || head->next == NULL)
return true;
ListNode *fast = head, *slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
//若奇数个节点，跳过中间节点
if (fast != NULL)
fast = slow->next;
else
fast = slow;
slow = head;
//头插法反转后半部分节点
ListNode *secHead = NULL;
while (fast)
{
ListNode *r = fast->next;
fast->next = secHead;
secHead = fast;
fast = r;
}
//比较两部分
fast = secHead;
while (fast)
{
if (fast->val != slow->val)
{
return false;
}//if
fast = fast->next;
slow = slow->next;
}//while
return true;
}
};