题目描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。（题目来源）
思路
我们需要找到传入链表的中间结点，并将中间结点及其后面结点进行反转，然后再将原链表的前半部分与反转后的后半部分进行比较，若相同，则该链表是回文结构，否则，不是回文结构。
1.找到链表的中间结点。
2.反转中间结点及其后面的结点。
3.比较链表的前半部分与后半部分的结点值，若相同则是回文结构，否则，不是回文结构。
将A指针指向的结点与RHead指针指向的结点进行比较，若相同，则两个指针后移，继续比较后面的结点，直到RHead指针指向NULL时，比较结束。
注意：就算传入的链表是结点数为奇数的回文结构，该思路也可以成功判断。
例如，以下链表反转其后半部分后，我们看似链表应该是这样的。
但反转后的链表并不是这样的，而应该是下面这样：
因为我们反转的是中间结点及其后面的结点，并没有对前面的结点进行任何操作，所以结点5所指向的结点应该还是结点7。
于是该链表的比较过程应该是这样的：1等于1，3等于3，5等于5，7等于7，然后RHead指针指向NULL。所以判断该链表是回文结构。
代码实现
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class PalindromeList {
public:
//查找链表的中间结点
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head;//快指针
struct ListNode* slow = head;//慢指针
while (fast&&fast->next)//遍历继续的条件
{
slow = slow->next;//慢指针一次走一步
fast = fast->next->next;//快指针一次走两步
}
return slow;//返回慢指针
}
//反转链表
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;//记录当前待头插的结点
struct ListNode* newhead = NULL;//新链表初始时为空
while (cur)//链表中结点头插完毕时停止循环
{
struct ListNode* next = cur->next;//记录下一个待头插的结点
cur->next = newhead;//将结点头插至新链表
newhead = cur;//新链表头指针后移
cur = next;//指向下一个待头插的结点
}
return newhead;//返回反转后的头指针
}
bool chkPalindrome(ListNode* A) {
ListNode* mid = middleNode(A);//查找链表的中间结点
ListNode* RHead = reverseList(mid);//反转后半段链表
while (RHead)//比较结束的条件
{
if (A->val != RHead->val)//不是回文结构
return false;
A = A->next;//指针后移
RHead = RHead->next;//指针后移
}
return true;//是回文结构
}
};