[每日一道小算法（五十三）] [链表]链表环的入口结点（剑指offer）

心已赠人 2023-07-06 14:42 25阅读 0赞

前言：  
以前做过链表是否有环的判断题，这道题是要求入口结点，着实想了好久。

### 题目描述 ###

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

### 解题思路 ###

判断有环的话，我们可以使用两个指针来完成，快慢指针。慢指针每次走一步，快指针每次走两步，如果有环，则一定会相遇。这个方法是用来判断链表是否有环，那么如何找到入口结点呢。  
我接着分析。我们找到快慢指针相遇的点p。我们假设环的入口结点在点q，从头结点到点q距离为A，q p 两点距离为B，p q 两点距离为C。因为快指针是慢指针的两倍速，且他们在p点相遇，则我们可以得到等式2（a+b） = a + b + c + b。根据这个等式，我们可以得出c = a。此时我们的slow指针继续保持原来的走法，新建一个slow2指针从头开始走。每次都走一个。这样当这两个指针相遇时，就是入口结点。因为a = c。不懂得结合下面的图，看一下就会明白了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]  
其实就是我们直到这个环有n个结点，让两个指针从开始走，p1先走n个结点，然后两个指针同时开始走，当他们相遇时那个结点就是入口结点。

### 代码样例 ###

package com.asong.leetcode.EntryNodeOfLoopLsit;
    
    /** * 链表环的入口结点 * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 */
    public class Solution { 
        public ListNode EntryNodeOfLoop(ListNode pHead)
        { 
            if(pHead==null)
            { 
                return null;
            }
            //快慢指针 快指针走两步 慢指针走一步 如果
            //快指针到达尾结点了，则无环，否则快慢指针相等则代表链表有环
            ListNode low = pHead;
            ListNode high = pHead;
            while(high!=null && high.next!=null)
            { 
                low = low.next;
                high = high.next.next;
                if(low == high)
                { 
                    //如果有环
                    ListNode slow2 = pHead;
                    while(slow2!=low){ 
                        slow2 = slow2.next;
                        low = low.next;
                    }
                    return slow2;
                }
            }
            return null;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200219200206531.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1,size_16,color_FFFFFF,t_70