拨付网站建设经费的请示,无锡网站建设收费,室内设计平面图库,宝安区网站建设公司1.前言
前五题在这http://t.csdnimg.cn/UeggB
后三题在这http://t.csdnimg.cn/gbohQ
给定一个链表#xff0c;判断链表中是否有环。http://t.csdnimg.cn/Rcdyc
记录每天的刷题#xff0c;继续坚持#xff01;
2.OJ题目训练
10. 给定一个链表#xff0c;返回链表开始… 1.前言
前五题在这http://t.csdnimg.cn/UeggB
后三题在这http://t.csdnimg.cn/gbohQ
给定一个链表判断链表中是否有环。http://t.csdnimg.cn/Rcdyc
记录每天的刷题继续坚持
2.OJ题目训练
10. 给定一个链表返回链表开始入环的第一个结点。 如果链表无环则返回 NULL
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
本题是上一题链接在上的延续不清楚的小码喵可以去上一篇博客观看一下。
方法一
思路 为了方便分析我们把示例图简化一下涉及一点数学思维大家做好准备。 我们依然按照上题来定义两个快慢指针fast一次前进两步slow一步 如果为环那么fast和slow终会在环中相遇这里假设已经相遇了。 注意以下的单位为节点数 入口点链表开始入环的第一个节点 相遇点fast和slow相遇的节点 假设起点到入口点长度:L 假设环的周长是:C假设入口点到相遇点的长度是:X 由于fast走过的距离是链表起点入口点 在环中移动的圈数必须转圈才能做到跟slow相遇 入口点到相遇点的距离
slow是链表起点入口点 入口点到相遇点的距离
fast走的距离是slow的两倍那么我们可以得出 fast移动的距离LCX slow移动的距离LX 两倍关系LCX2(LX) 但是上面fast公式的C我们要画上一个问号因为fast可能在环中不止会转一圈可能会转很多圈环足够小所以我们再改进公式得到 fast移动的距离Ln*CX n为fast在环中循环的圈数 slow移动的距离LX 两倍关系Ln*CX2(LX) ↓ L n*C - X 得出关系链表头走到起点的距离 n倍的周长再减去相遇点到起点的距离 进而得出一个指针从表头走一个指针从相遇点走那么他们会在入口点相遇! 附源代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast;struct ListNode *slow;fast slow head;while(fastfast-nextslow-next){fastfast-next-next;slowslow-next;if(fast slow) //相遇{struct ListNode *tou fast; //相遇点,相遇时再创建节约空间while(head!tou) //向下继续走直到他们相遇就是起点{head head -next;tou tou - next;}return tou; }}return NULL; //无法相遇则不为环形链表
}
方法二
本题还有一个极为简单的解法但是相对繁琐我们要用到之前刷过的一题。CV一下
这里给大家一个链接看看大家能不能自己想出方法160. 相交链表 - 力扣LeetCode
思路
我们可以利用更新奇的办法分割链表来把一个链表变为两个再利用相交链表的方法来求出他们的起点。 当fast和slow相遇时我们记录这个相遇点 之后再记录下一个点我们就可以把相遇点断开称为newhead 这样环形链表和newhead组成的表就可以运用相交链表的方法达到入口点既交点的节点了 如图红色和紫色既两个相交链表
注意事项
相交链表那块要足够清楚我们是将问题牵线搭桥到那里去的所以要足够理解直接CV
附源代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///返回相交链表相交节点的函数struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curAheadA;struct ListNode *curBheadB;int lenA1,lenB1; //链表的长度至少为1while(curA-next) //计算链表A的长度及尾节点{lenA; //顺便计算表长curAcurA-next;}while(curB-next){lenB;curBcurB-next;}if(curA!curB){return NULL; //两边的为节点不相同那根本不是相交链表}int gapabs(lenA-lenB); //abs为取绝对值struct ListNode *longlistheadA; //假设A为长节点这里我们利用替身来表示长表struct ListNode *shortlistheadB; //就可以节省很多判断语句if(lenBlenA) //若B长侧替换{longlistheadB;shortlistheadA;}while(gap--){longlistlonglist-next; //先走差值步}while(longlist!shortlist) //不等于则同时向前遍历直到相等{longlistlonglist-next;shortlistshortlist-next;}return longlist; //返回第一个相等值
}//此题函数
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast;struct ListNode *slow;fast slow head;while(fastfast-nextslow-next){fastfast-next-next;slowslow-next;if(fast slow) //相遇{struct ListNode *tou fast; //相遇点,相遇时再创建节约空间struct ListNode *newhead tou-next; //新表头为相遇的下一个节点tou-next NULL; //将相遇点断开return getIntersectionNode(newhead, head);}}return NULL; //无法相遇则不为环形链表
}
