推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

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

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
public class Solution {
   

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
   
        
    }
}

参考思路：

我们设置一个快指针，一个慢指针；

从链表头节点开始，快指针每次走 2 个结点，慢指针每次走 1 个结点；

因为有环，且快指针速度比慢指针快，所有快指针必然会超过慢慢指针一圈从而追上慢指针。

我们假设：

链表头结点到入口结点的距离为 x ；

环入口结点到相遇结点的距离为 y （顺时针）；

相遇结点到环入口结点的距离为 z （顺时针）；

（我们假设慢指针还没跑完一圈，快指针在跑第二圈的时候就与慢指针相遇了。虽然圈比较小的时候，可能要多跑一圈，但是并不影响我们的结果，可以去画几个图试一下看看，所以这里简化一下。）

那么：

快指针走过的距离就是：x + y + z + y ;

慢指针走过的距离就是：x + y ;

又因为快指针速度是慢指针的 2 的两倍，所以快指针走过的距离也是慢指针的两倍；

所以可得：

x + y + z + y = 2 (x + y)

化简一下：z = x ；

也就是相遇点到环入口结点的距离等于链表头结点到入口结点的距离。

那么当快慢指针相遇之后，我们让其中一个指针回到链表头结点，然后两个指针速度都设置为 1 ，这两个指针就会在环入口结点相遇。

参考实现：

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
public class Solution {
   

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
   
        if (pHead == null || pHead.next == null) {
   
            return null;
        }
        ListNode slow = pHead; //慢指针
        ListNode fast = pHead; //快指针
        while (fast != null && fast.next != null) {
   
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
   
                fast = pHead;
                while(slow != fast){
   
                    slow = slow.next;
                    fast = fast.next;
                }
                if (slow == fast){
   
                    return slow;
                }
            }
        }
        return null;
    }
}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！