LeetCode 142——环形链表II(JAVA)

待我称王封你为后i 2021-11-11 13:52 214阅读 0赞

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 `null`。

为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 `-1`，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
    输出：tail connects to node index 1
    解释：链表中有一个环，其尾部连接到第二个节点。

![1517990-20190729160504962-1910658469.png][]

![circularlinkedlist.png][]

示例 2：

输入：head = [1,2], pos = 0
    输出：tail connects to node index 0
    解释：链表中有一个环，其尾部连接到第一个节点。

![1517990-20190729160513964-724426441.png][]

![circularlinkedlist_test2.png][]

示例 3：

输入：head = [1], pos = -1
    输出：no cycle
    解释：链表中没有环。

![1517990-20190729160521167-145365588.png][]

直接上代码：

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    /*首先根据快慢指针判断是否有环，无环直接返回null
    有环，则根据*/
    public class Solution 
    {
        public ListNode detectCycle(ListNode head) 
        {
            if(head==null||head.next==null)
            {
               return null;
           }
           ListNode fast=head,slow=head;
           while(fast!=null&&fast.next!=null)
           {
               slow=slow.next;
               fast=fast.next.next;
               if(fast==slow)//确定有环
               {
                   break;
               }
           }
           
           if(fast==slow)//
           {
               ListNode q=head;
               while(q!=slow)
               {
                   q=q.next;
                   slow=slow.next;
               }
               return q;
           }
            else
            {
               return null;
            }
           
       }
    
    }

首先判断快慢指针一定会相遇的数学证明参考这篇博文：[https://blog.csdn.net/mucaoyx/article/details/81395782][https_blog.csdn.net_mucaoyx_article_details_81395782]

接下来看一下为什么当p指针和slow相遇的节点就是入环的节点。

好了，看一下啊我的分析，严格数学的证明.......

![1517990-20190730164425018-1701091782.png][]

好了，看了上面的介绍，绝对可以搞懂这道题了！！！！！

加油加油！！！！

![circularlinkedlist_test3.png][]

转载于:https://www.cnblogs.com/jiameng991010/p/11264456.html

[1517990-20190729160504962-1910658469.png]: /images/20211109/0e3ce162ede74457882051cf7a4ca4cc.png
[circularlinkedlist.png]: /images/20211109/bb6ec774b7364196b3ef9d45af584063.png
[1517990-20190729160513964-724426441.png]: /images/20211109/66601b3b34b64d829de843d75feb8645.png
[circularlinkedlist_test2.png]: /images/20211109/74fcf39bfb8b40fc88ec4788debd3843.png
[1517990-20190729160521167-145365588.png]: /images/20211109/53eaa13858284f80b53c6d0e05df594a.png
[https_blog.csdn.net_mucaoyx_article_details_81395782]: https://blog.csdn.net/mucaoyx/article/details/81395782
[1517990-20190730164425018-1701091782.png]: /images/20211109/46ba6f3a5776461eac8c867e67cc6e95.png
[circularlinkedlist_test3.png]: /images/20211109/efa0610f857c436f8b19f2cfa7fe6c1a.png