前言

小伙伴们大家好啊！今天我们为大家带来一篇有关判断链表回文的文章。大家一旦想到回文，那么第一感觉是无从下手，因为我们可能需要在原地修改链表，然后进行比较。但是当你看完这篇文章的时候，相信你一定会有一个更深层次的了解。

一，题目分析

1.1什么是回文

回文，就是一组数，顺着读和反着读是一样的，比如：12321。这样的一组数我们称为回文数。那么链表回文当然也是一样的结构。

1.2题目分析

如下图所示，我们看到题目中要求，我们必须使用时间复杂度为O(n)，空间复杂度为O(1)的算法。那么就说明我们是不能使用额外的空间，只能在原链表的基础上进行改变，判别。

二，解题思路

情况一：

那么鉴于上面的题目，我们有以下分析：

上图所示，是一个回文链表，那么我们认为既然是回文，肯定会有一个中间节点，我们可以将该节点作为新链表的头节点，然后将其反转。

这样我们就得到了下面的图：

那么我们看到，当新链表反转之后，得到的便是一个新链表。这个链表当然不同于原链表的结构，因为我们是将中间节点及之后的链表进行了反转。此时节点 4 的 next 依旧指向节点 5 ，但是这一点也不影响我们判断是否是回文。

现在假设是有两个新链表，然后我们对其进行比较，两个链表的 4 节点比较完事之后。最后一个比较的节点都是 5 ，此时表示原链表是回文结构。

情况二:

上面所示，是一种很常见的回文结构，那么当然还有另一种情况：123321，这样子也是回文。

但是我们知道，一般情况下，如果对于一组数个数为偶数的话，那么它的中间节点将是第二个中间节点，也就是这里我们有两个 3 ，但是我们用后面那个 3 作为该链表的中间节点，然后进行翻转，得到两个新链表也是一样的。

tips：

因为比较的循环的结束，是通过判别后面得到的新链表是否结束来决定的。所以我们不用担心，这种情况下，原头结点所在的链表还链接在原中间节点，没有全部比较完。因为我们已经达到了目的，已经判别完是否是回文结构了。

三，源码分享

因为这里我们用到了额外的两个接口。分别是查找中间节点，以及反转链表。如有小伙伴有需要，可自行食用哦！

LeetCode：206. 反转链表_憨憨二号耶！的博客-CSDN博客

LeetCode：876. 链表的中间节点_憨憨二号耶！的博客-CSDN博客

struct ListNode* middleNode(struct ListNode* head){struct ListNode*fast=head;struct ListNode*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}struct ListNode* reverseList(struct ListNode* head){struct ListNode*n1=NULL;struct ListNode*n2=head;if(head==NULL)return NULL;struct ListNode*n3=head->next;while(n2){//核心n2->next=n1;//移动n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;
}class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode*slow=middleNode(A);struct ListNode*head=reverseList(slow);struct ListNode*cur=A;while(head){if(cur->val != head->val){return false;}else{head=head->next;cur=cur->next;}}return true;}
};

好的，那么对于本文的分享到此就结束啦！如有问题，还请指正呀！

链表回文（牛客网：OR36 链表的回文结构）

前言