剑指offer55:链表中环的入口结点
2019-08-29 08:55:30来源:博客园 阅读 ()
剑指offer55:链表中环的入口结点
1 题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。2 思路和方法
这是一个典型的链表中查找环的问题,基本思路是,首先设置两个快慢指针slow和fast,并且快指针fast每次前进两步,慢指针slow每次前进一步,假定当相遇的时候,设慢指针在环中走了k步,设环之外的部分长为x,环的长度
为c,则快指针一共走了:x+b1∗c+k步,(b1?为快指针在环中走的圈数)慢指针一共走了:x+b2∗c+k步,(b2?为快指针在环中走的圈数)因为快指针的速度是慢指针的两倍。
那么可以得到:
2∗(x+b2∗c+k)==x+b1∗c+k; 得到x为m∗c−k
其中m=b1−2∗b2m=b1?−2∗b2?,慢指针在圈中还剩下的步数c−k。我们可以发现,如果此时让快指针设置为从原点开始,每次只前进一步,那么由于x为m∗c−k,慢指针剩下的步数也只剩c−k,这样,如果两个指针同时出发的话,
最终一定会相遇的。这时,慢指针有可能已经走了m-1圈,并在环的入口处和快指针相撞,此时求出该相遇的点即可。
3 C++核心代码
1 /* 2 struct ListNode { 3 int val; 4 struct ListNode *next; 5 ListNode(int x) : 6 val(x), next(NULL) { 7 } 8 }; 9 */ 10 class Solution { 11 public: 12 ListNode* EntryNodeOfLoop(ListNode* pHead) 13 { 14 if(pHead==NULL||pHead->next==NULL) 15 { 16 return NULL; 17 } 18 ListNode* slow=pHead; 19 ListNode* fast=pHead; 20 while(fast!=NULL&&fast->next!=NULL) 21 { 22 slow=slow->next; 23 fast=fast->next->next; 24 if(slow==fast) 25 { 26 fast=pHead; 27 while(fast!=slow) 28 { 29 fast=fast->next; 30 slow=slow->next; 31 } 32 if(fast==slow) 33 { 34 return slow; 35 } 36 } 37 } 38 return NULL; 39 } 40 };View Code
参考资料
https://blog.csdn.net/qq_29462849/article/details/90400558
原文链接:https://www.cnblogs.com/wxwhnu/p/11429099.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- leetcode 反转链表 2020-06-06
- 数据结构—链表 2020-05-29
- STL之list 2020-04-30
- 单链表 2020-03-31
- DSA_04:链表 2020-03-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash