环形链表II（142）

题目

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明

不允许修改给定的链表。

进阶：

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

示例

输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点

解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点

解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1 输出：返回 null

解释：链表中没有环。

提示

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

算法

Set

使用Set保存遍历过的每一个节点，如果有环，那么环的入口就是第一个在Set中存在的节点

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
const detectCycle = (head) => {
	const set = new Set();
	while (head) {
		if (set.has(head)) {
			return true;
		} else {
			set.add(head);
			head = head.next;
		}
	}
	return false;
};

标记

在每一个遍历过的节点上新增flag属性用来判断链表是否成环

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
const detectCycle = (head) => {
	while (head) {
		if (head.flag) {
			return head;
		} else {
			head.flag = true;
			head = head.next;
		}
	}
	return null;
};

快慢指针

快慢指针同时从起点出发，我们设定：

• 起点到环入口的距离称为a
• 在环中相遇时慢指针走过的环中的距离为b，令
• 慢指针没走的环的距离为c

那么相遇时：

• 慢指针走过的距离是：a+b
• 快指针走过的距离是a+n(b+c)+b，n为走的圈数

因为每时每刻快指针都是慢指针走过的距离的2倍，所以：

a+n(b+c)+b = a+b

化简得：

a = c+(n-1)(b+c)

即环外得距离 = n-1圈环的长度 + 相遇时慢指针没有走的环的距离

所以我们设定一个指针从头节点开始，以相同的速度和慢指针同时移动，当他们相遇时（新的指针走过了环外的距离，慢指针走完了环中剩余的距离），即为环的入口

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
const detectCycle = (head) => {
	let fast = head,
		slow = head;
	while (fast) {
		slow = slow.next;
		if (fast.next) {
			fast = fast.next.next;
		} else {
			return null;
		}
		if (fast === slow) {
			let node = head;
			while (node !== slow) {
				node = node.next;
				slow = slow.next;
			}
			return slow;
		}
	}
	return null;
};