最好的生日礼物,国庆ppt,米果网
这是一个典型的链表中查找环的问题,基本思路是,首先设置两个快慢指针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圈,并在环的入口处和快指针相撞,此时求出该相遇的点即可。
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
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论