Question

Given a singly linked list, determine if it is a palindrome. 判断链表是否为回文

Algorithm

需要解决的问题： 1、找到中心的位置（一快一慢指针，快的一次走两步，慢的一次走一步） 2、以中心拆分链表，并反转后半部分的链表 （http://blog.csdn.net/u011391629/article/details/52164389）

找到中心位置后，反转要分结点个数为奇数和偶数两种情况，也可以不分。

以1->2->3和1->2->3->4为例 如下图，奇数要反转slow->next,偶数要反转slow。 结束条件：fast!=NULL && fast->next!=NULL

如果是下图这种情况，就不用分奇数偶数的情况，反转slow->next就可以。 结束条件：fast->next!=NULL && fast->next->next!=NULL

Accepted Code： 不分奇偶：

class Solution { public: ListNode* reverseList(ListNode* head) { if(head==NULL || head->next==NULL) return head; ListNode* pre=NULL; ListNode* p=head; ListNode* pNext=NULL; while(p!=NULL) { pNext=p->next; p->next=pre; pre=p; p=pNext; } return pre; } bool isPalindrome(ListNode* head) { if(head==NULL || head->next==NULL) return true; ListNode* slow=head; ListNode* fast=head; while(fast->next!=NULL && fast->next->next!=NULL) { slow=slow->next; fast=fast->next->next; } slow=reverseList(slow->next); while(slow!=NULL) { if(slow->val != head->val) return false; slow=slow->next; head=head->next; } return true; } };

分奇偶：

class Solution { public: ListNode* reverseList(ListNode* head) { if(head==NULL || head->next==NULL) return head; ListNode* pre=NULL; ListNode* p=head; ListNode* pNext=NULL; while(p!=NULL) { pNext=p->next; p->next=pre; pre=p; p=pNext; } return pre; } bool isPalindrome(ListNode* head) { if(head==NULL || head->next==NULL) return true; ListNode* slow=head; ListNode* fast=head; while(fast!=NULL && fast->next!=NULL) { slow=slow->next; fast=fast->next->next; } if(fast!=NULL) { slow=reverseList(slow->next); } else { slow=reverseList(slow); } while(slow!=NULL) { if(slow->val != head->val) return false; slow=slow->next; head=head->next; } return true; } };