上海比较好的网站建设公司,做淘宝那样的网站,看强 的,计算机软件开发专业#x1f451;个人主页#xff1a;啊Q闻 #x1f387;收录专栏#xff1a;《数据结构》 #x1f389;前路漫漫亦灿灿 前言 今日的习题是关于链表的#xff0c;分别是链表的回文结构和相交链表的判断。 链表的回文结构
题目为#xff1a;链表的回文结… 个人主页啊Q闻 收录专栏《数据结构》 前路漫漫亦灿灿 前言 今日的习题是关于链表的分别是链表的回文结构和相交链表的判断。 链表的回文结构
题目为链表的回文结构_牛客题霸_牛客网
这道题目没有C语言的运行环境我们可以用CC兼容C 思路为 我们实现判断是否为回文结构要先找到中间节点然后将中间节点开始的后部分逆置所以我们要调用前面学习过的寻找中间节点和反转链表的函数【数据结构】链表习题之链表的中间节点和合并两个有序链表-CSDN博客 【数据结构】链表习题之反转链表和删除链表中等于给定值 val 的所有节点-CSDN博客 然后比较后半部分和前半部分判断是否相同。 代码实现
struct ListNode*reverse(struct ListNode*head)//反转链表
{if(headNULL){return head;}struct ListNode*n1,*n2,*n3;n1NULL;n2head;n3head-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3){n3n3-next;}}return n1;
}
struct ListNode*middleNode(struct ListNode*head)//寻找中间节点
{struct ListNode*slow,*fast;slowfasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode*midmiddleNode(A);//将节点后部分逆置struct ListNode*rmidreverse(mid);while(Armid)//比较两部分当有一个为空时循环结束{if(A-val!rmid-val){return false;}AA-next;rmidrmid-next;}return true;}
};
相交链表
题目为. - 力扣LeetCode 思路为 注意我们比较的是节点的指针而不是节点的值因为节点不相交的时候其节点的值也有可能相等。 我们可以先找A和B链表的尾节点如果尾节点相同则代表这两个链表一定相交然后我们再求长度差让长的链表先走长度差长的链表走完长度差后A和B两个链表再一起走。 时间复杂度分析我们利用这种方法其时间的复杂度为:遍历A链表为N遍历B链表为N然后减去长度差后再一起遍历为NNNN3N,即ON)。 在这个代码的实现过程中我们会用到假设法来简化长短链表的判断是一个很实用的方法。 代码实现 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode*curAheadA;struct ListNode*curBheadB;int lenA0;int lenB0;while(curA-next)//A和B链表遍历找尾节点{lenA;curAcurA-next;}while(curB-next){lenB;curBcurB-next;}if(curA!curB){return NULL;}int gapabs(lenA-lenB);//abs为绝对值//假设法假设A为长链表B为短链表然后再利用一个判断不成立就交换struct ListNode*longlistheadA;struct ListNode*shortlistheadB;if(lenAlenB){longlistheadB;shortlistheadA;}while(gap--)//长链表先走{longlistlonglist-next;}while(longlist!shortlist)//A和B链表一起走{longlistlonglist-next;shortlistshortlist-next;}return longlist;//该处返回长短链表均可
}
详解 假设法我们用假设法就可以不用分别去讨论AB,还是AB,简化了代码 感谢大家阅读希望对你有帮助 如果对你有帮助的话三连支持一下吧
