链表中环的入口结点

今天药忘吃喽~ 2022-05-24 05:06 177阅读 0赞

![这里写图片描述][70]  
一、分析  
判断链表有环的算法中出现过的策略，分别按1x和2x速度遍历，总会相遇。假设环长为n。  
容易知道，当1x的指针p1和2x的指针p2相遇时，p1走了x步，p2走了2x步，而p2比p1多走的，有两部分：  
(1)环内部，p1还没有走过的；（2）环内部，p1和p2重合的  
这两部分加起来就是整个环。那么其实p2比p1多走的就是这么一个环的距离（假设距离为n），也就是说

2x-x=n

![这里写图片描述][70 1]  
假设Z为相遇点即:

2*(a+b) = a+b+c+b
      得出a=c,即|xy|=xz弧

那么此时让slow(fast)回到起点，fast(slow)依然停在z，两个同时开始走，一次走一步那么它们最终会相遇在y点(环入口节点)，正是环的起始点

import java.util.HashSet;
     class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    
    public class Solution {
    
        //方法一:巧用Set值
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
             if(pHead==null||pHead.next==null)
                 return null;
              HashSet<ListNode>hash=new HashSet<>();
              while (pHead!=null) {
                  hash.add(pHead);
                  pHead=pHead.next;
                  if(hash.contains(pHead)){
                      break;
                  }
              }
    
             return pHead;
        }
    
        //方法二:快慢指针法
        public ListNode EntryNodeOfLoop2(ListNode pHead){
             if(pHead==null||pHead.next==null)
                 return null;
             ListNode one=pHead;
             ListNode two=pHead;
             while(two!=null)
             {
                     one=one.next;
                     two=two.next.next;
                     if(one==two)
                     {
                           two=pHead;
                           while(one!=two)
                           {
                                 one=one.next;
                                 two=two.next;
                           }
                           if(one==two)
                               return one;
    
                     }
    
             }
               return null;
    
        }
    
        public static void main(String[]args){
            //System.out.println("Hello");
            ListNode head=new ListNode(1);
            head.next=new ListNode(2);
            head.next.next=new ListNode(3);
            ListNode p4=new ListNode(4);
            head.next.next.next=p4;
            p4.next=head.next;
            Solution ss=new Solution();
            System.out.println(ss.EntryNodeOfLoop2(head).val);
        }
    }

![这里写图片描述][70 2]

[70]: /images/20220524/1756e4806ec44eb8aec21ea01f1d84ce.png
[70 1]: /images/20220524/0d38fa48376b434eac8985d038206099.png
[70 2]: /images/20220524/b3935faf0786463ea24774603b5b06d2.png

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关链表中环的入口结点 (C++牛客网)

/ struct ListNode { int val; struct ListNode next; ListN

阳光穿透心脏的1/2处/ 2022年09月10日 10:15/ 0 赞/ 144 阅读

相关链表中环的入口结点

![这里写图片描述][70] 一、分析判断链表有环的算法中出现过的策略，分别按1x和2x速度遍历，总会相遇。假设环长为n。容易知道，当1x的指针p1和2x的指针

今天药忘吃喽~/ 2022年05月24日 05:06/ 0 赞/ 177 阅读

相关编程题：链表中环的入口结点

题目描述一个链表中包含环，请找出该链表的环的入口结点。思路：假设x为环前面的路程，a为环入口到相遇点的路程， c为环的长度

╰+攻爆jí腚メ/ 2022年05月21日 09:45/ 0 赞/ 150 阅读

相关【剑指Offer】55链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。时间限制：1秒；空间限制：32768K；本题知识点：链表解题思路思路

迈不过友情╰/ 2022年04月21日 23:36/ 0 赞/ 198 阅读

相关剑指offer:链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 AC C++ Solution: 解题思路：还是使用两个指针，一个fast，

小鱼儿/ 2022年04月10日 09:23/ 0 赞/ 200 阅读

相关【剑指Offer】（链表）链表中环的入口结点

题目链接：[https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11

深藏阁楼爱情的钟/ 2022年03月17日 14:24/ 0 赞/ 226 阅读

相关剑指Offer-链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。解题思路—HashMap：使用HashMap存储链表结点，当链表结点重复时，即有环

曾经终败给现在/ 2022年02月14日 03:22/ 0 赞/ 213 阅读

相关链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 / @author gentleKay

た入场券/ 2021年11月09日 08:40/ 0 赞/ 275 阅读

相关剑指offer 链表中环的入口结点

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。链表结点定义

待我称王封你为后i/ 2021年11月05日 23:56/ 0 赞/ 281 阅读

相关剑指offer：链表中环的入口结点

试题：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。代码： / public class ListNode {

Myth丶恋晨/ 2021年06月24日 16:10/ 0 赞/ 391 阅读