链表的回文结构的判定（C语言）怎会如此简单！！！

题目

链接: 题目
描述：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

举例：

1->2->2->1

返回：true

思路分析

首先，回文结构是链表的一半反转后跟另一半相同，因此，我们可以先找到中间节点，将后半部分给翻转，再跟前半部分对比即可。
这里我们需要三个步骤：
找到中间节点
反转链表
链表对比

如何找到中间节点

看到这里的小伙伴有思路了吗？没错！跟你想的一样，我们可以使用快慢指针，快慢指针指的是使用两个指针，慢指针走一步，快指针走两步，快指针走到最后一个节点（奇数）或者走到空（偶数），则慢指针走到了中间节点。
嘻嘻，有没有一种恍然大悟的感觉，我相信你一定是有的，那到底该如何做呢？请看代码：

 ListNode *slow = A;//A是头节点
        ListNode *fast = A;
        while(fast && fast->next)
        {
            slow = slow->next;//慢指针走一步
            fast = fast->next->next;//快指针走两步
        }

如果fast=NULL，则有偶数个节点
在这里插入图片描述

如果fast->next=NULL,则有奇数个节点
在这里插入图片描述

如何实现反转链表

我们可以使用三个指针变量来实现，创建三个指针变量， $\colorbox{CadetBlue}{一个指向NULL,一个指向头节点，第三个指向头节点的下一个节点}$ 。
在这里插入图片描述
废话不多说，请看代码的实现：

 		ListNode * p1 = NULL;
        ListNode * p2 = slow;
        ListNode * p3 = p2->next;
        while(p2)
        {
            p2->next = p1;
            p1 = p2;
            p2 = p3;
            if(p3!=NULL)//这里需要防止p3为空
            p3 = p3->next;
        }

嘻嘻！是不是有点小简单…

链表的对比

第一个链表是反转后的链表，第二个原始的链表，第二个节点的指向为data=3的节点
在这里插入图片描述

实际上，图像应该这样画！
在这里插入图片描述
是不是要清晰很多！！！
请看代码：

 ListNode*pp1 = p1;
         ListNode *pp2 = A;
        while(pp1&&pp2)
        {
            if(pp1->val != pp2->val)
            return false;
            pp1 = pp1->next;
            pp2 = pp2->next;
        }

完整代码

 bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode *slow = A;
        ListNode *fast = A;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode * p1 = NULL;
        ListNode * p2 = slow;
        ListNode * p3 = p2->next;
        while(p2)
        {
            p2->next = p1;
            p1 = p2;
            p2 = p3;
            if(p3!=NULL)
            p3 = p3->next;
        }
        ListNode*pp1 = p1;
         ListNode *pp2 = A;
        while(pp1&&pp2)
        {
            if(pp1->val != pp2->val)
            return false;
            pp1 = pp1->next;
            pp2 = pp2->next;
        }
        return true;

    }