寻找链表环的入口

清疚 2022-10-01 06:45 144阅读 0赞

[（寻找链表环的入口）][Link 1]  
题解：

这个连同I都是很经典的题啦，刷CC150时候就折磨了半天。

其实就推几个递推公式就好。。首先看图（图引用自CC150）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]  
从链表起始处到环入口长度为：a，从环入口到Faster和Slower相遇点长度为：x，整个环长为：c。

明确了以上信息，就可以开始做运算了。。

假设从开始到相遇，Slower走过的路程长为s，由于Faster的步速是Slower的2倍，那么Faster在这段时间走的路程长为2s。

而对于Faster来说，他走的路程还等于之前绕整个环跑的n圈的路程nc，加上最后这一次遇见Slower的路程s。

所以我们有：

2s = nc + s

对于Slower来说，他走的路程长度s还等于他从链表起始处到相遇点的距离，所以有：

s = a + x

通过以上两个式子代入化简有：

a + x = nc
    
                    a = nc - x
    
                    a = (n-1)c + c-x
    
                    a = kc + (c-x)

那么可以看出，c-x，就是从相遇点继续走回到环入口的距离。上面整个式子可以看出，如果此时有个pointer1从起始点出发并且同时还有个pointer2从相遇点出发继续往前走（都只迈一步），那么绕过k圈以后， pointer2会和pointer1在环入口相遇。这样，换入口就找到了。

//找到链表中环的入口点
        public static Node findLoopPort(Node head){
            //首先判断头结点是否为null
            if(head==null||head.next==null)
                return null;
            Node fast = head,slow=head;
            //找到相遇点fast
            while (true) {
                if (fast == null || fast.next == null) {
                    return null;
                }
                //找到
                slow = slow.next;
                fast = fast.next.next;
    
                if(fast == slow)
                    break;
            }
            //相遇点与链表头分别设定一个指针,每次各走一步,相遇第一个点即为环入口点
            slow = head;//slow back to start point
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow; //when slow == fast, it is where cycle begins
        }
        @Test
        public void testIsLoop() {
            Node n1 = new Node(1);
            Node n2 = new Node(2);
            Node n3 = new Node(3);
            Node n4 = new Node(4);
            Node n5 = new Node(5);
    
            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
            n4.next = n5;
            n5.next = n2;  //构造一个带环的链表,去除此句表示不带环
            boolean b = LinkedList.IsLoop(n1);
            System.out.println(b);//true
    
            Node loopPort = LinkedList.findLoopPort(n1);
            System.out.println(loopPort.data);
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 1]

[Link 1]: https://www.cnblogs.com/springfor/p/3862125.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]: /images/20220119/56758f276146418bae7e31d0cf65845a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 1]: /images/20220119/a36a004e55714f288549493045c583de.png