图解LeetCode——142. 环形链表 II

2023-05-18 本文已影响0人爪哇缪斯

一、题目

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。

二、示例

2.1> 示例 1：

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

2.2> 示例 2：

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

2.3> 示例 3：

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

提示：

链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引

进阶：

你是否可以使用 O(1) 空间解决此题？

三、解题思路

根据题目描述，我们需要返回链表开始入环的第一个节点。那么我们会最先想到的解题方式就是，创建一个Set集合，然后遍历整个链表，当遍历到某个节点的时候，发现该节点已经存在于Set集合中，则表示找到了入环的第一个节点，返回该节点即可。

但是本题在进阶部分提出了一个问题：你是否可以使用 O(1) 空间解决此题？那么我们就不能通过创建Set集合去解决这个问题了。那么我们来分析一下这个链表，以下图为例，我们将其拆分为非环形状a和环形形状b两个部分。那么采用快慢指针（fast&slow）的方式去遍历链表，由于快指针的速度是慢指针的2倍，所以我们可以得出以下结论，即：

fast指针行走的距离 = slow指针行走的距离 * 2；（我们简写为：fast= 2*slow）

那么fast指针肯定先进入到循环链表中，随后slow指针才会进入到循环链表中，那么无论在链表中哪个节点处fast和slow相遇，我们都可以得出一个结论，即：

fast指针在循环链表中行走的距离 = slow指针在循环链表中行走的距离 * n圈 * b；（例如：跑步比赛被套圈了，此处我们简写为 fast = slow * nb）

如果以slow与fast在环中相遇的那个节点node为基准，那么，fast指针行走的总长度其实包含两个部分：

【第1部分】从链表head开始到node的距离为：slow的行走距离；
【第2部分】以node为起始节点，fast行走的距离为：N圈b*；

因此，我们可以得出如下推论：

【因为】fast = 2slow，并且fast = slow + Nb;
【所以】slow = N*b;

那么入环的第一个节点会是在哪个位置呢？其实就是a + Nb，那么我们就可以通过slow指针与fast指针的两次相遇，来计算出这个节点的位置了：

【步骤1】slow行走1步，fast行走2步，当fast与slow相遇的时候，就是slow的行走距离，也就是Nb。
【步骤2】此时将fast指针指向head头节点，然后fast变为每次只行走1步，那么当fast行走了a距离的时候，就满足了 a + Nb长度了，fast和slow必然会相遇，而且是在入环的第一个节点位置上。

以上就是本题的解题思路了，在下图中，通过举例的方式，一步一步的演示其执行逻辑，如下是步骤1的执行图例，请见下图所示：

如下是步骤2的执行图例，请见下图所示：

四、代码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        boolean isfast = true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = isfast ? fast.next.next : fast.next;
            if (slow == fast) { 
                if (isfast) { // 第一次相遇
                    isfast = false;
                    // 如果此时slow指向head，直接返回fast节点即可
                    if (slow == head) return fast; 
                    else fast = head;
                } else return fast;
            }
        }
        return null;
    }
}
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞 & 分享。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」