给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
2 思路和方法 这是一个典型的链表中查找环的问题，基本思路是，首先设置两个快慢指针slow和fast，并且快指针fast每次前进两步，慢指针slow每次前进一步，假定当相遇的时候，设慢指针在环中走了k步，设环之外的部分长为x，环的长度
为c，则快指针一共走了：<span id="MathJax-Element-1-Frame" class="MathJax" data-mathml="x+b1∗c+k x+b_1*c+k">x+b1∗c+k步，（b1为快指针在环中走的圈数）慢指针一共走了：x<span id="MathJax-Element-3-Frame" class="MathJax" data-mathml="x+b2∗c+k x+b_2*c+k">+b2∗c+k<span class="MathJax" data-mathml="b1 b_1">步,（<span class="MathJax" data-mathml="b2 b_2">b2为快指针在环中走的圈数）因为快指针的速度是慢指针的两倍。
那么可以得到：
2<span id="MathJax-Element-5-Frame" class="MathJax" data-mathml="2∗(x+b2∗c+k)==x+b1∗c+k 2*(x+b_2*c+k)== x+b_1*c+k">∗(x+b2∗c+k)==x+b1∗c+k； 得到x<span id="MathJax-Element-2-Frame" class="MathJax" data-mathml="b1 b_1"><span id="MathJax-Element-4-Frame" class="MathJax" data-mathml="b2 b_2">为<span id="MathJax-Element-7-Frame" class="MathJax" data-mathml="m∗c−k m*c-k">m∗c−k
<span id="MathJax-Element-2-Frame" class="MathJax" data-mathml="b1 b_1"><span id="MathJax-Element-4-Frame" class="MathJax" data-mathml="b2 b_2"><span id="MathJax-Element-7-Frame" class="MathJax" data-mathml="m∗c−k m*c-k"> 其中<span id="MathJax-Element-8-Frame" class="MathJax" data-mathml="m=b1−2∗b2 m=b_1-2*b_2">m=b1−2∗b2m=b1−2∗b2，慢指针在圈中还剩下的步数<span id="MathJax-Element-9-Frame" class="MathJax" data-mathml="c−k c-k">c−k。我们可以发现，如果此时让快指针设置为从原点开始，每次只前进一步，那么由于<span id="MathJax-Element-10-Frame" class="MathJax" data-mathml="x x">x为<span id="MathJax-Element-11-Frame" class="MathJax" data-mathml="m∗c−k m*c-k">m∗c−k，慢指针剩下的步数也只剩<span id="MathJax-Element-12-Frame" class="MathJax" data-mathml="c−k c-k">c−k，这样，如果两个指针同时出发的话，
最终一定会相遇的。这时，慢指针有可能已经走了m-1圈，并在环的入口处和快指针相撞，此时求出该相遇的点即可。
3 C++核心代码![]()
View Code
参考资料https://blog.csdn.net/qq_29462849/article/details/90400558
收藏
淘帖
踩
