142-环形链表 II
- 题目描述
- 我的解题思路(Floyd判圈)(快慢指针)
-
- 代码
- 时间复杂度&空间复杂度
题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，
pos
仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
- 你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围 [0, 104] 内
- -105 <= Node.val <= 105
- pos 的值为 -1 或者链表中的一个有效索引
我的解题思路(Floyd判圈)(快慢指针)
在做过leetcode-寻找重复数这题之后已经回想起了Floyd判圈的结论,然后解决环形链表的入口问题就非常简单了
结论:
- 一个快指针fast,一个慢指针slow都指向头结点，fast一次走两步，slow一次走一步，如果链表存在环，那么必然fast和slow会有一个重合点。
- 一个指针before指向头结点,一个指针after指向重合点，速度相同，然后走到的新的重合点就是环形链表的入口。
代码
//detect: 探测
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
//慢指针
ListNode slow = head;
//快指针
ListNode fast = head;
// 这边要先走一次，再判断，不然刚开始就满足条件，就出bug了，找了半天
do {
fast = fast.next.next;
slow = slow.next;
} while (fast != null && fast.next != null && fast != slow);
if (fast == null || fast.next == null) {
return null;
}
//指向头结点
ListNode before = head;
//指向重合的结点
ListNode after = fast;
while (before != after) {
before = before.next;
after = after.next;
}
return before;
}
时间复杂度&空间复杂度
时间复杂度: O(N)
空间复杂度: O(1)