题述：对于一个链表，请设计一个时间复杂度为o(n),额外空间复杂度为o(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度<=900
测试样例：
输入：1->2->2->1
输出：true
题目分析：
回文就是对称结构。题目所让求解的肯定是在单链表的前提下，要是双链表就很好求了，但是单链表的缺陷就是不能倒着走，只能正着走。
有一种想法是，创建数组大小900的数组，如int a[900],然后遍历链表，把每个节点的值都放入此数组中，用数组来判断回文。这样做oj上是能跑过的，但是不可行，因为这种方法的空间复杂度是o(n)，因为你链表开多长你数组就得开多大去存储，这是一个侥幸方法。
正确的思路：
①、找链表的中间节点，偶数个结点就找后一个。至于怎么找，我之前代码有写过
②、将指向链表中间节点的指针（包括本身）后面的所有节点逆置，如果和中间节点之前的节点内容相同，那就符合回文结构
③、找到中间节点后，即使逆置，还可以使中间节点的前一个节点指向中间节点，可以不用解开（改变指向），因为不解开（不改变指向）也可以判断是否为回文结构，相反如果解开链表，会更麻烦。
//判断链表的回文结构
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>struct ListNode
{int val;struct ListNode* next;
};
//1、找中间节点的函数
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow, * fast;fast = slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
//2、逆置链表的函数
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1, * n2, * n3;n1 = NULL;n2 = head;n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}return n1;
}
bool chkPalindrome(struct ListNode* A)
{struct ListNode* mid = middleNode(A);//找到中间节点struct ListNode* rHead = reverseList(mid);//将中间节点（包括本身）后的节点翻转struct ListNode* curA = A;struct ListNode* curR = rHead;while (curA && curR)//因为对于有偶数个结点来说，curR会先碰到NULL，作为结束标志{//所以这里判断条件只写curR即可，在是回文的前提下。因为奇数节点时，curA和curR同时为空，//偶数是curR先为空if (curA->val != curR->val){return false;}else{curA = curA->next;curR = curR->next;}}return true;
}
int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));n1->val = 1;n2->val = 2;n3->val = 3;n4->val = 2;n5->val = 1;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = NULL;int Istrue = chkPalindrome(n1);printf("该链表是否为回文结构:(1真/0假)%d", Istrue);return 0;
}
