赞
踩
目录
小伙伴们大家好啊!今天我们为大家带来一篇有关判断链表回文的文章。大家一旦想到回文,那么第一感觉是无从下手,因为我们可能需要在原地修改链表,然后进行比较。但是当你看完这篇文章的时候,相信你一定会有一个更深层次的了解。
回文,就是一组数,顺着读和反着读是一样的,比如:12321。这样的一组数我们称为回文数。那么链表回文当然也是一样的结构。
如下图所示,我们看到题目中要求,我们必须使用时间复杂度为O(n),空间复杂度为O(1)的算法。那么就说明我们是不能使用额外的空间,只能在原链表的基础上进行改变,判别。
那么鉴于上面的题目,我们有以下分析:
上图所示,是一个回文链表,那么我们认为既然是回文,肯定会有一个中间节点,我们可以将该节点作为新链表的头节点,然后将其反转。
这样我们就得到了下面的图:
那么我们看到,当新链表反转之后,得到的便是一个新链表。这个链表当然不同于原链表的结构,因为我们是将中间节点及之后的链表进行了反转。此时节点 4 的 next 依旧指向节点 5 ,但是这一点也不影响我们判断是否是回文。
现在假设是有两个新链表,然后我们对其进行比较,两个链表的 4 节点比较完事之后。最后一个比较的节点都是 5 ,此时表示原链表是回文结构。
上面所示,是一种很常见的回文结构,那么当然还有另一种情况:123321,这样子也是回文。
但是我们知道,一般情况下,如果对于一组数个数为偶数的话,那么它的中间节点将是第二个中间节点,也就是这里我们有两个 3 ,但是我们用后面那个 3 作为该链表的中间节点,然后进行翻转,得到两个新链表也是一样的。
因为比较的循环的结束,是通过判别后面得到的新链表是否结束来决定的。所以我们不用担心,这种情况下,原头结点所在的链表还链接在原中间节点,没有全部比较完。因为我们已经达到了目的,已经判别完是否是回文结构了。
因为这里我们用到了额外的两个接口。分别是查找中间节点,以及反转链表。如有小伙伴有需要,可自行食用哦!
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;
- }
- };
好的,那么对于本文的分享到此就结束啦!如有问题,还请指正呀!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。