142. 环形链表 II（中等）

叁歲伎倆 2022-09-09 02:10 118阅读 0赞

Leetcode链接：[142. 环形链表 II][142. _ II]

### 题目描述 ###

> 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 `null`。  
>   
>   
> 为了表示给定链表中的环，我们使用整数 `pos`来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 `-1`，则在该链表中没有环。注意，`pos` 仅仅是用于标识环的情况，并不会作为参数传递到函数中。  
>   
>   
> 说明：不允许修改给定的链表。  
>   
>   
> 进阶：  
> 你是否可以使用 `O(1)` 空间解决此题？

示例 1：  
![在这里插入图片描述][66d6b852c03e450b92823c5bb2bdc007.png]

> 输入：head = \[3,2,0,-4\], pos = 1  
> 输出：返回索引为 1 的链表节点  
> 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

![在这里插入图片描述][11292ef7c30c4a96a8abf8a4738d0bb3.png]

> 输入：head = \[1,2\], pos = 0  
> 输出：返回索引为 0 的链表节点  
> 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

![在这里插入图片描述][d8662427e3e94b61b40509158edda13a.png]

> 输入：head = \[1\], pos = -1  
> 输出：返回 null  
> 解释：链表中没有环。

提示：

> 链表中节点的数目范围在范围 \[0, 104\] 内  
> \-105 <= Node.val <= 105  
> `pos` 的值为 `-1` 或者链表中的一个有效索引

### 题解 ###

*  这类链表题目一般都是使用双指针法解决的，例如寻找距离尾部第K个节点、寻找环入口、寻找公共尾部入口等。

**算法流程**：

1.**双指针第一次相遇**： 设两指针 `fast`，`slow` 指向链表头部 `head`，`fast` 每轮走 `2` 步，slow 每轮走 `1` 步；

*  **第一种结果**： `fast` 指针走过链表末端，说明链表无环，直接返回 `null`；
    
     *  TIPS: 若有环，两指针一定会相遇。因为每走 `1` 轮，`fast` 与 `slow`的间距 `+1`，`fast` 终会追上 `slow`；
 *  **第二种结果**： 当`fast == slow`时， 两指针在环中 **第一次相遇** 。下面分析此时`fast` 与 `slow`走过的 **步数关系** ：
    
     *  设链表共有 `a+b`个节点，其中 链表头部到链表入口 有 `a` 个节点（不计链表入口节点）， **链表环** 有 `b` 个节点（这里需要注意，`a` 和 `b` 是未知数，例如图解上链表 `a=4` , `b=5`）；设两指针分别走了 `f`，`s` 步，则有：
    
    1.  `fast` 走的步数是`slow`步数的 `2` 倍，即 `f = 2s`；（**解析**： `fast` 每轮走 `2` 步）
    2.  `fast` 比 `slow`多走了 `n` 个环的长度，即 `f = s + nb`；（ **解析**： 双指针都走过 `a` 步，然后在环内绕圈直到重合，重合时 `fast` 比 `slow` 多走 **环的长度整数倍** ）；
    3.  以上两式相减得：`f = 2nb`，`s = nb`，即`fast`和`slow` 指针分别走了 `2n`，`n` 个 **环的周长** （注意： `n` 是未知数，不同链表的情况不同）。

2.**目前情况分析：**

*  如果让指针从链表头部一直向前走并统计步数`k`，那么所有 走到链表入口节点时的步数 是：`k=a+nb`（先走 aa 步到入口节点，之后每绕 1 圈环（ b 步）都会再次到入口节点）。
 *  而目前，`slow` 指针走过的步数为 `nb` 步。因此，我们只要想办法让 slow 再走 `a` 步停下来，就可以到环的入口。
 *  但是我们不知道 `a` 的值，该怎么办？依然是使用双指针法。我们构建一个指针，此指针需要有以下性质：此指针和`slow` 一起向前走 `a` 步后，两者在入口节点重合。那么从哪里走到入口节点需要 `a` 步？答案是链表头部`head`。

3.**双指针第二次相遇**：

*  `slow`指针 **位置不变** ，将`fast`指针重新 **指向链表头部节点** ；`slow`和`fast`同时每轮向前走 `1` 步；
    
     *  TIPS：此时 `f = 0`，`s = nb` ；
 *  当 `fast` 指针走到`f = a`步时，`slow` 指针走到步`s = a+nb`，此时 **两指针重合，并同时指向链表环入口 。**

4.**返回`slow`指针指向的节点**。

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            if(head == null || head.next == null) return null;
    
            ListNode fast = head;
            ListNode slow = head;
    
            while(fast != null && fast.next != null){
        
                fast = fast.next.next;
                slow = slow.next;
    
                if(fast == slow) break;
            }
    
            //不存在环；
            if(fast == null || fast.next == null) return null;
    
            //存在环
            fast = head;
            while(fast != slow){
        
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }

时间复杂度：O(N)  
空间复杂度：O(1)

[142. _ II]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[66d6b852c03e450b92823c5bb2bdc007.png]: /images/20220829/30543350e36f4c63921f5a1e06c02591.png
[11292ef7c30c4a96a8abf8a4738d0bb3.png]: /images/20220829/4f1d1d806f4b4433ba1927c5722725aa.png
[d8662427e3e94b61b40509158edda13a.png]: /images/20220829/bc6d5cb898ed440b84c80d4300ff6f35.png