原文题目：
读题：
判断链表是否为回文链表，比如1->2->2->1，1->2->3->2->1就是回文链，前半段和后半段对称的，这里提供思路：
1）既然是回文链，那么链表翻转后，与原链表是一样的，那么就简化为了链表翻转
2）翻转整个链表不如翻转后半段，再与前半段比较，效果一样
3）那就要找到中间节点位置进行后半段翻转，翻转可以用栈也可以直接翻转，这里采用直接翻转法，链表翻转可以参考python实现链表翻转
以下为AC代码：
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
/*链表翻转操作*/
ListNode* reverse(ListNode *head)
{
if (NULL == head)
{
return NULL;
}
ListNode* pre = head;
ListNode* cur = head->next;
ListNode* temp = NULL;
pre->next = NULL;
while (cur)
{
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
bool isPalindrome(ListNode* head)
{
ListNode* fast = head;
ListNode* slow = head;
ListNode* other = NULL;
/*空链表或者只有一个节点的链表为回文链表*/
if (NULL == head)
{
return true;
}
if (NULL == head->next)
{
return true;
}
/*一个指针走两步，一个指针走一步，当快指针走到链表尾部，慢指针就到了中间节点*/
while (fast&&fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
/*翻转后半段节点*/
other = reverse(slow);
/*后半段与原链表比较*/
while (other&&head)
{
if (other->val != head->val)
{
return false;
}
other = other->next;
head = head->next;
}
return true;
}
};
void main()
{
Solution s;
ListNode node1(1);
ListNode node2(2);
ListNode node3(3);
ListNode node4(2);
ListNode node5(1);
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;
node5.next = NULL;
cout << s.isPalindrome(&node1) << endl;
getchar();
}