网站建设 发布,wordpress网站维护,电子商务代运营,广州做网站优化哪家专业#x1f680;write in front#x1f680; #x1f4dc;所属专栏#xff1a;初阶数据结构 #x1f6f0;️博客主页#xff1a;睿睿的博客主页 #x1f6f0;️代码仓库#xff1a;#x1f389;VS2022_C语言仓库 #x1f3a1;您的点赞、关注、收藏、评论#xff0c;是对… write in front 所属专栏初阶数据结构 ️博客主页睿睿的博客主页 ️代码仓库VS2022_C语言仓库 您的点赞、关注、收藏、评论是对我最大的激励和支持 关注我关注我关注我你们将会看到更多的优质内容 文章目录前言例题1方法1方法2例题2完整代码总结前言 在前面的练习中我们简单练习了链表的相关题目今天我们在来做一些拓展
例题1
在这里插入图片描述
方法1 在上一篇博客里面我们讲述了快慢指针的概念通过步长的差异处理环的问题。而这道题我们要寻找入口点我们该如何处理呢
首先我们假设
起始点到入口的长度为L入口到相遇点的距离为X环的长度为C。
接下来我们通过快慢指针的两个性质快指针是慢指针步数的两倍快慢指针最后相遇列出一个方程 由得出的结论我们可以看出如果让一个指针a从起点出发另一个指针b从相遇点出发如果是闭环则他们一定会相遇这里我们并不需要算出n的值因为n的值是是让a指针多走n-1个整圈不影响和b指针相遇。 下面我们来看看代码
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode*slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){struct ListNode*curhead;while(cur!slow){curcur-next;slowslow-next;}return slow;}} return NULL;
}方法2 如果同学们在做题时无法自己推出这个结论那么此时我们也可以将相遇点断开此时就变成了寻找公共节点的题目了。
例题2 对于这道题目大家可能最先会想到计数器的方法通过记录每个random的位置在拷贝的链表里面找到对于位置依次连接。但是这样会导致时间复杂度非常的低下ON^2 为了降低复杂度就不得不使用另外一种方法。要降低时间复杂度我们就希望能快速的找到原节点的拷贝节点。怎么找呢
1.拷贝节点链接在原节点后面
2.此时拷贝节点的random就是原节点random-next
3.拷贝节点解下来链接成新链表最后将原链表还原。
完整代码
struct Node* copyRandomList(struct Node* head)
{//第一步struct Node*curhead;while(cur){struct Node* newnode(struct Node*)malloc(sizeof(struct Node));struct Node* nextcur-next;cur-nextnewnode;newnode-nextnext;newnode-valcur-val;curnext;}//第二步curhead;while(cur){struct Node*prevcur-next;if(cur-randomNULL){prev-randomNULL;}else{prev-randomcur-random-next;}curcur-next-next;}//第三步struct Node* newheadNULL,*newtailNULL;curhead;while(cur){struct Node*prevcur-next;struct Node*nextprev-next;if(newheadNULL){newheadnewtailprev;}else{newtail-nextprev;newtailprev;}curnext;}return newhead;
}总结 链表的相关题目到这里就结束了当然同学们也可以去oj看看其他题oj题 更新不易辛苦各位小伙伴们动动小手三连走一走 ~ ~ ~ 你们真的对我很重要最后本文仍有许多不足之处欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正 专栏订阅 每日一题 c语言学习 算法 智力题 初阶数据结构 更新不易辛苦各位小伙伴们动动小手三连走一走 ~ ~ ~ 你们真的对我很重要最后本文仍有许多不足之处欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正
