题目来源：
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
题目描述：
本题的难点在于时间复杂度为O(n)，空间复杂度为O(1)。
代码实现：
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast = head, * slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } struct ListNode* reverse(struct ListNode* head) { struct ListNode* prev = NULL, * cur = head, * next = NULL; while (cur) { //尾插 next = cur->next; cur->next = prev; prev = cur; //迭代 cur = next; } return prev; } class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here struct ListNode* mid = middleNode(A); struct ListNode* rmid = reverse(mid); while (rmid) { if (rmid->val != A->val) return false; rmid = rmid->next; A = A->next; } return true; } };
思路分析：
因为回文结构是正着读反着读是一样的，因此我们找到链表的中间结点，然后从中间节点开始逆置到尾结点，然后用逆置后的链表与原链表的前半段对比，如果每个结点的 val 都相等，就说明此链表是回文结构。
实现过程：
1.使用快慢指针，初始化都指向原链表的头，慢指针一次走一步，快指针一次走两步，快指针走到空或快指针的 next 走到空时，慢指针指向的就是中间结点。
2.找到中间结点后，从中间结点开始到尾结点进行逆置。
这里讲的不够细致，找中间结点与逆置分别是两篇文章，里面讲的比较细致。
找中间结点：http://t.csdn.cn/z3vm5
逆置链表/反转链表：http://t.csdn.cn/Jt38p
我们分别将这两个功能封装成函数使用。
3.以逆置之后的链表头结点作为循环条件（这里其实不难发现逆置后的链表与原链表的长度相等），遍历整个逆置之后的链表，与原链表的 val 对比，如果存在哪个结点的val 不相等就返回 false，如果遍历完整个逆置后的链表都相等就返回 true。
这样的解法可以实现题目的要求：本题的难点在于时间复杂度为O(n)，空间复杂度为O(1)。
如果大牛的您看到有什么问题留言给我，我一定会认真看的，谢谢您。如果您看了觉得有收获，关注 + 点赞支持一下呗。
*** 本篇结束 ***
