题目链接

牛客网

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路

快慢指针

慢指针移动 1 步，快指针移动 2 步，相遇在环内，将环分成a、b长度。
因为快指针速度是慢指针的两倍
(F+a) * 2 = F + n(a+b) + a，快指针在环内多走了n圈，简化后
F = (n-1)(a+b) + b
如果这时候将快指针放回head处，快慢指针一次直走一步，则他们会在F处相遇。

更简单的思路：
反正多走了多少圈不影响结果，取n=1，(F+a) * 2 = F + a + a + b，有F = b，所以只需要将fast放回head，一步一步走即可

题中是肯定有环的，如果可能没有环，参考第二份代码

public class Solution {
   
    public ListNode EntryNodeOfLoop(ListNode pHead){
   
        if (pHead==null || pHead.next==null) return null;
        ListNode slow = pHead.next, fast = pHead.next.next;
        while (fast != slow) {
   
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = pHead;
        while (fast != slow) {
   
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

public class Solution {
   
    public ListNode EntryNodeOfLoop(ListNode head) {
   
        ListNode fast = head，slow = fast;
        while (fast!=null && fast.next!=null) {
   
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
   
                while (slow != head) {
   
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        return null;
    }
}