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) 额外空间下完成？
解题思路：
对于数组，判断是否是回文很好办，只需要用两个指针，从两端往中间扫一下就可以判定。
对于单向列表，首先想到的是，将列表复制一份到数组中，然后用上面的方法就可以了，O(n) 时间， O(n)额外空间。
如果是 O(1)额外空间，就没有思路，在网上找了下，找到一个解决方案。值得注意的是，这个方案执行过程中，会改变原来列表的结构。
- 利用快指针、慢指针定位列表的中间元素。快指针每次走两步，而慢指针每次只走一步，当快指针走到列表末尾，慢指针刚好在列表中间。
- 根据慢指针，将列表前、后两半分开，并将后半列表翻转。
- 对前半列表 和 翻转后的后半列表依次对比，判断原列表是否是回文的。
bool isPalindrome(ListNode* head) {
if(head == NULL || head->next == NULL){
return true;
}
if(head->next->next == NULL){
return (head->val == head->next->val);
}
if(head->next->next->next == NULL){
return (head->val == head->next->next->val);
}
// 找列表中间元素
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != NULL && fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
// 翻转后半部分元素
ListNode* newHead = slow->next;
slow->next = NULL;
ListNode* p = newHead->next;
ListNode* pNext = newHead->next->next;
newHead->next = NULL;
while (pNext != NULL) {
p->next = newHead;
newHead = p;
p = pNext;
pNext = pNext->next;
}
p->next = newHead;
newHead = p;
// 判断是否是回文
ListNode* p1 = head;
ListNode* p2 = newHead;
while (p2 != NULL) {
if (p1->val != p2->val) {
return false;
}
p1 = p1->next;
p2 = p2->next;
}
return true;
}