剑指offer55:链表中环的入口结点
程序员文章站
2022-03-25 22:26:44
1 题目描述 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。 2 思路和方法 这是一个典型的链表中查找环的问题,基本思路是,首先设置两个快慢指针slow和fast,并且快指针fast每次前进两步,慢指针slow每次前进一步,假定当相遇的时候,设慢指针在环中走了k步,设环之 ......
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 };
参考资料
https://blog.csdn.net/qq_29462849/article/details/90400558
推荐阅读
-
《剑指offer》-- 两个链表的第一个公共结点、链表中环的入口结点、删除链表中的重复结点
-
剑指offer——面试题37:两个链表的第一个公共结点
-
牛客 剑指Offer 单链表判断是否有环 以及找出环的入口点
-
剑指offer55:链表中环的入口结点
-
剑指offer56:删除链表中重复的结点,排序的链表中,删除重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
-
剑指offer 之 链表中环的入口节点
-
剑指offer——链表中环的入口节点
-
【剑指offer】23.链表中环的入口节点
-
剑指offer——链表中环的入口节点
-
[剑指offer-23]链表中环的入口节点