🎁个人主页:我们的五年
🔍系列专栏:每日一练
🌷追光的人,终会万丈光芒
目录
🏝问题描述:
🏝问题分析:
步骤一:查找链表的中间节点
步骤二:对包括中间节点以后的节点进行逆置
步骤三:两个头指针相互往后遍历
🏝节点为计数时分析:
🏝最终代码:
前言:
这道题在链表中属于较难的题目,但是题目中我们用已经学过得基本步骤去改一下就很简单了,这道题应用的基本步骤就是:
●查找链表的中间节点
●逆置链表
这些基本步骤我都放在了这篇文章中:链表必写的四道基础题
牛客网链接:链表的回文结构_牛客题霸_牛客网
下面就让我们来看看这道题怎么解决:
🏝问题描述:
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例:
1->2->2->1返回:true
🏝问题分析:
假如上面是一个双链表,我们只要那到链表的头节点和尾节点,然后两个头都往中间进行遍历,如果出现val不相等,我们就返回false,最后没有提前返回false,我们就返回true。
可惜上面的不是双向链表,但是我们想,单链表我们只能1>2,然后2>1,刚好和1>2和1>2相反,如果我们可以把后面的链表逆置一下,我们就可以做到前面一半也是1>2,后面一半也是1开头,然后1>2,这样就能对上了,下面我们来进行实现
先以上面的测试用例为例子:
步骤一:查找链表的中间节点
我们先查找中间节点,如果节点个数为偶数,那么我们找到的就是中间节点的第二个节点,比如上面的例子我们找到的就是第三个节点。
查找中间节点的函数的实现:
struct ListNode* MidNode(struct ListNode* ps)
{
struct ListNode* fast=ps;
struct ListNode* slow=ps;
if(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
步骤二:对包括中间节点以后的节点进行逆置
实现函数:
ListNode* reverselist(ListNode* ps)
{
ListNode* newhead=NULL;
while(ps)
{
ListNode* pnext=ps->next;
ps->next=newhead;
newhead=ps;
ps=pnext;
}
return newhead;
}
对后半段的节点进行逆置以后,链表就变成这样:
步骤三:两个头指针相互往后遍历
也就是两个1节点为头,然后每走一步,比较两个节点的val。如果不相同我们就返回false,如果相同就一直一直往后面走,走到一个为NULL为止,走到NULL还没有提前返回false,我们就返回true。
🏝节点为计数时分析:
上面我们分析的是节点为偶数个,下面我们来看看节点个数为奇数个时的情况:
现在我们查找中间节点就是3节点,然后我们进行逆置以后,链表就变成这样了:
这种情况我们好像我们进行遍历也是没有什么问题的,所以我们只要去查找中间节点,然后进行逆置,然后遍历判断,这道题就完成了。
🏝最终代码:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
//查找中间节点的函数
struct ListNode* MidNode(struct ListNode* ps)
{
struct ListNode* fast=ps;
struct ListNode* slow=ps;
if(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
//逆置链表
ListNode* reverselist(ListNode* ps)
{
ListNode* newhead=NULL;
while(ps)
{
ListNode* pnext=ps->next;
ps->next=newhead;
newhead=ps;
ps=pnext;
}
return newhead;
}
bool chkPalindrome(ListNode* A) {
// write code here
struct ListNode* mid=MidNode(A);
struct ListNode* remid=reverselist(mid);
//进行判断
while(A&&remid)
{
if(A->val!=remid->val)
return false;
A=A->next;
remid=remid->next;
}
return true;
}
};
总结:
这道题算是对链表的一个小小提升,这道题目也告诉了我,一定要学好基本的知识点,把基本的知识点用的很熟练以后,才能去解决很难得题目,后期我还会带来很多值得思考,值得我们写一写的题目。如果觉得这篇文章写的好的铁子可以点点关注,祝大家天天开心!