您现在的位置是:首页 >学无止境 >图解LeetCode——142. 环形链表 II网站首页学无止境
图解LeetCode——142. 环形链表 II
一、题目
给定一个链表的头节点 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
=2
slow
,并且fast
=slow
+N
b
;
【所以】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^)/ ~ 「干货分享,每天更新」