👑个人主页:啊Q闻
🎇收录专栏:《数据结构》
🎉前路漫漫亦灿灿
前言
今日的习题是关于链表的,分别是链表的回文结构和相交链表的判断。
链表的回文结构
题目为:链表的回文结构_牛客题霸_牛客网
这道题目没有C语言的运行环境,我们可以用C++,C++兼容C
思路为:
我们实现判断是否为回文结构,要先找到中间节点,然后将中间节点开始的后部分逆置,所以我们要调用前面学习过的寻找中间节点和反转链表的函数【数据结构】链表习题之链表的中间节点和合并两个有序链表-CSDN博客
【数据结构】链表习题之反转链表和删除链表中等于给定值 val 的所有节点-CSDN博客
然后比较后半部分和前半部分,判断是否相同。
代码实现:
struct ListNode*reverse(struct ListNode*head)//反转链表
{
if(head==NULL)
{
return head;
}
struct ListNode*n1,*n2,*n3;
n1=NULL;
n2=head;
n3=head->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
{
n3=n3->next;
}
}
return n1;
}
struct ListNode*middleNode(struct ListNode*head)//寻找中间节点
{
struct ListNode*slow,*fast;
slow=fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
struct ListNode*mid=middleNode(A);//将节点后部分逆置
struct ListNode*rmid=reverse(mid);
while(A&&rmid)//比较两部分,当有一个为空时,循环结束
{
if(A->val!=rmid->val)
{
return false;
}
A=A->next;
rmid=rmid->next;
}
return true;
}
};
相交链表
题目为:. - 力扣(LeetCode)
思路为:
注意:我们比较的是节点的指针,而不是节点的值,因为节点不相交的时候,其节点的值也有可能相等。
我们可以先找A和B链表的尾节点,如果尾节点相同,则代表这两个链表一定相交,然后我们再求长度差,让长的链表先走长度差,长的链表走完长度差后,A和B两个链表再一起走。
时间复杂度分析:我们利用这种方法,其时间的复杂度为:遍历A链表为N,遍历B链表为N,然后减去长度差后再一起遍历为N,N+N+N=3N,即O(N)。
在这个代码的实现过程中,我们会用到假设法,来简化长短链表的判断,是一个很实用的方法。
代码实现:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode*curA=headA;
struct ListNode*curB=headB;
int lenA=0;
int lenB=0;
while(curA->next)//A和B链表遍历找尾节点
{
++lenA;
curA=curA->next;
}
while(curB->next)
{
++lenB;
curB=curB->next;
}
if(curA!=curB)
{
return NULL;
}
int gap=abs(lenA-lenB);//abs为绝对值
//假设法:假设A为长链表,B为短链表,然后再利用一个判断,不成立就交换
struct ListNode*longlist=headA;
struct ListNode*shortlist=headB;
if(lenA<lenB)
{
longlist=headB;
shortlist=headA;
}
while(gap--)//长链表先走
{
longlist=longlist->next;
}
while(longlist!=shortlist)//A和B链表一起走
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;//该处返回长短链表均可
}
详解:
假设法:我们用假设法,就可以不用分别去讨论A>B,还是A<B,简化了代码
😃感谢大家阅读,希望对你有帮助😄
如果对你有帮助的话,三连支持一下吧