[编程题]链表中环的入口结点
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
数据范围： n≤10000n\le10000 n ≤ 1 0 0 0 0 ，1<=结点值<=100001<=结点值<=10000 1 < = 结 点 值 < = 1 0 0 0 0
要求：空间复杂度 O(1)O(1) O ( 1 )，时间复杂度 O(n)O(n) O ( n )
例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
输入描述:
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
输出描述:
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
示例1
输入
{1,2},{3,4,5}
输出
3
说明
返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
示例2
输入
{1},{}
输出
"null"
说明
没有环，返回对应编程语言的空结点，后台程序会打印"null"
示例3
输入
{},{2}
输出
2
说明
环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2
-
思路：
设置快慢指针，都从链表头出发，快指针每次**走两步**，慢指针一次**走一步**，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次 **走一步** ，最终相遇于环入口(结论2)。以下是两个结论证明：两个结论：
1、设置快慢指针，假如有环，他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。
**证明结论1** ：设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇（因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上）。证明结论2：
设：
链表头到环入口长度为-- a
环入口到相遇点长度为-- b
相遇点到环入口长度为-- c
则：相遇时
快指针路程=a+(b+c)k+b ，k>=1 其中b+c为环的长度，k为绕环的圈数（k>=1,即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾）。
慢指针路程=a+b
快指针走的路程是慢指针的两倍，所以：
（a+b） 2=a+(b+c)k+b**
化简可得：
**a=(k-1)(b+c)+c **这个式子的意思是： *链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度** 。其中k>=1,所以 k-1>=0 圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。
-
-
第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
-
第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。
-
public class Solution { ListNode EntryNodeOfLoop(ListNode pHead){ if(pHead == null || pHead.next == null) return null; ListNode p1 = pHead; ListNode p2 = pHead; while(p2 != null && p2.next != null ){ p1 = p1.next; p2 = p2.next.next; if(p1 == p2){ p2 = pHead; while(p1 != p2){ p1 = p1.next; p2 = p2.next; } if(p1 == p2) return p1; } } return null; } }
-
发表回复