142. 环形链表 II

🟠   🔖  哈希表 链表 双指针  🔗 力扣 LeetCode

题目

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, returnnull.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to ( 0-indexed ). It is -1 if there is no cycle. Note thatpos is not passed as a parameter.

Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1

Output: tail connects to node index 1

Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0

Output: tail connects to node index 0

Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1

Output: no cycle

Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

题目大意

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

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

不允许修改 链表。

解题思路

可以通过快慢指针的方法来解决。

1. 定义两个指针，一个慢指针 slow，一个快指针 fast，初始位置都在链表的头部。
2. 使用循环，每轮循环中慢指针走一步，快指针走两步。
3. 如果链表中存在环，快指针最终会追上慢指针，两者会相遇。如果链表中不存在环，快指针会先到达链表的末尾。
4. 如果相遇，将其中一个指针重新放置在链表头部，然后两个指针以相同的速度向前移动，每次移动一步。
5. 当两个指针再次相遇时，相遇点即为环的入口点。

这个方法的原理证明如下：

假设链表头到环的入口点的距离为 a 步，环的入口点到相遇点的距离为 b 步，环的长度为 c 步。那么，在第一次相遇时，慢指针 slow 走了 a + b 步，快指针 fast 走了 a + b + k * c 步（其中 k 是快指针在环中转了 k 圈）。

由于快指针的速度是慢指针的两倍，所以：2(a + b) = a + b + k * c

整理得：a = (k - 1) * c + (c - b)

这意味着从相遇点继续走 a 步，将再次到达环的入口点。我们重新将 slow 指针放到链表头，然后 slow 和 fast 每次都移动一步，最终它们将在环的入口点相遇。

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表中的节点数量。

  • 在第一阶段（找环阶段），快指针 fast 以两倍速度遍历链表，而慢指针 slow 以正常速度遍历链表。当链表中存在环时，快慢指针最终会在环中相遇。由于每次移动都会减少两者之间的距离，因此最坏情况下需要遍历整个链表，这一部分的时间复杂度为 O(n)。
  • 在第二阶段（找环入口），两个指针从相遇点和头结点开始分别每次移动一步，最终会在环的入口处相遇。这个过程最多也需要遍历 O(n) 的节点。

• 空间复杂度：O(1)，只使用了常数空间来存储变量。

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
	let slow = head;
	let fast = head;
	while (fast !== null && fast.next !== null) {
		slow = slow.next;
		fast = fast.next.next;
		if (slow == fast) {
			slow = head;
			while (slow !== fast) {
				slow = slow.next;
				fast = fast.next;
			}
			return slow;
		}
	}
	return null;
};

相关题目

题号	标题	题解	标签	难度
141	环形链表	[✓]	哈希表 链表 双指针
287	寻找重复数	[✓]	位运算 数组 双指针 1+