142. 环形链表 II

╰+攻爆jí腚メ 2023-02-12 13:27 14阅读 0赞

# 题目： #

[142. 环形链表 II][142. _ II]  
[链表中环的入口结点][Link 1]  
[\[编程题\]链表中环的入口结点][Link 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

## 1. 题解一：利用set求解 ##

遍历链表的时候，用一个容器set依次装入链表的节点，如果发现有重复的节点，那么该节点就是链表的环的入口节点。

## 2. 题解二：双指针（快慢指针） ##

1.  解释一：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]
2.  解释二：  
    ![在这里插入图片描述][20200526124722385.png]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]
3.  解释三：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]
4.  解释四：

采用双指针的方法（这个方法还可以用来判断链表中有没有环），一个快指针一个慢指针，快指针一次走两步，慢指针一次走一步，
    如果链表中有环，那么两个指针一定就可以相遇，并且相遇的地方，一定在环的某处。
    
    设相遇的地方距环的入口点一边有a个节点，一边有b个节点，链表除环以外有x个节点，环中一共有c个节点（c=a+b）
    
    那么可以得到如下关系式，用b = c -a表示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]  
5. 解释五：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 8]  
也就说，让慢指针指向环上的相遇点，快指针指向链表的头结点，同时以步长为1往后走，其碰头的那个结点，就是入口结点。

# 代码： #

## 1. 代码一：利用set求解 ##

// 方法1：
    public static ListNode detectCycle(ListNode head) { 
        Set<ListNode> set = new HashSet<>(); // 哈希表去重
        ListNode temp = null;
        while(head != null)
        { 
            if(set.contains(head))
            { 
                temp = head;
                break;
            }
            set.add(head);
            head = head.next;
        }
        return temp;
    }

## 2. 代码二：双指针（快慢指针） ##

// 方法2：
    public static ListNode detectCycle(ListNode head) { 
        if(head == null || head.next == null)
        { 
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        boolean flag = false;
        while(fast != null && fast.next != null)
        { 
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow)
            { 
                flag = true;
                break;
            }
        }
        if(flag == true)
        { 
            fast = head;
            while(fast != slow)
            { 
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        return null;
    }

# 参考： #

1.  [环形链表 II][II]
2.  [环形链表 II（双指针法，清晰图解）][II 1]
3.  [详细图解(肯定看的明白)][Link 3]
4.  [双指针清晰题解，真正从数学上证明][Link 4]
5.  [我对第二阶段的理解][Link 5]
6.  [详细通俗的思路分析，多解法][Link 6]
7.  [快慢指针（Java、C++、Python）][Java_C_Python]
8.  [判断一个单链表是否有环，若有环，求进入环中的第一个节点][Link 7]
9.  [\[算法总结\] 17 题搞定 BAT 面试——链表题][17 _ BAT]
10. [\[剑指offer\] 链表中环的入口结点][offer_]
11. [链表中环的入口节点][Link 8]
12. [《剑指offer》——链表中环的入口结点][offer]

[142. _ II]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[Link 1]: https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
[Link 2]: https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200526124155937.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200526125929518.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[20200526124722385.png]: https://img-blog.csdnimg.cn/20200526124722385.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200526124752630.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200526125309776.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200526125343945.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200526125611867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200526130222444.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200526130331806.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200526130343290.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[II]: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode/
[II 1]: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
[Link 3]: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/xiang-xi-tu-jie-ken-ding-kan-de-ming-bai-by-xixili/
[Link 4]: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/shuang-zhi-zhen-qing-xi-ti-jie-zhen-zheng-cong-shu/
[Link 5]: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/wo-dui-di-er-jie-duan-de-li-jie-by-fei-er-10/
[Link 6]: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--33/
[Java_C_Python]: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/kuai-man-zhi-zhen-by-liweiwei1419-2/
[Link 7]: https://www.jianshu.com/p/530191c3b10b
[17 _ BAT]: https://juejin.im/post/5b8df65b51882542e32ab3df
[offer_]: https://weiweiblog.cn/entrynodeofloop/
[Link 8]: https://segmentfault.com/a/1190000019667627
[offer]: https://blog.csdn.net/shansusu/article/details/50285735