简单刷题记录2.22

牛客网剑指Offer

链表中环的入口结点

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

自己没想出来怎么做的，抄了答案，答案用的是双指针，快慢指针，中间涉及到了一些数学的思路。考虑两种情况，一种如下，环很大

如果有环，那么快指针走过的路径就是图中a+b+c+b，慢指针走过的路径就是图中a+b，因为在相同的时间内，快指针走过的路径是慢指针的2倍，所以这里有a+b+c+b=2*(a+b)**，整理得到a=c**，也就是说图中a的路径长度和c的路径长度是一样的。

在相遇的时候再使用两个指针，一个从链表起始点开始，一个从相遇点开始，每次他们都走一步，直到再次相遇，那么这个相遇点就是环的入口。

第二种是环很小，

这种情况下当快慢指针在环上相遇的时候，快指针有可能在环上转了好几圈，我们假设相遇的时候快指针已经在环上转了n圈。

那么相遇的时候快指针走过的路径就是a+b+(b+c)*n，（b+c其实就是环的长度），慢指针走过的路径是a+b。由于相同时间内快指针走过的路径是慢指针的2倍。

所以有a+b+(b+c)*n=2*(a+b)**，整理得到a+b=n*(b+c)，也就是说a+b**等于n个环的长度。

我们还可以使用两个指针，一个从链表的起点开始，一个从相遇点开始，那么就会出现一种情况就是，一个指针在路径a上走，一个指针一直在环上转圈，最终会走到第一种情况。

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        
        if(pHead.next == pHead){
            return pHead;
        }
        if(pHead.next == null){
            return null;
        }
        
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast!=null&&fast.next!=null&&slow!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                while(slow!=pHead){
                    slow = slow.next;
                    pHead = pHead.next;
                }
                return slow;
            }
        }
        return null;
    }
}