环形链表（141）

题目

给定一个链表，判断链表中是否有环。

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

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶

你能用 O(1)（即，常量）内存解决此问题吗？

示例

输入：head = [3,2,0,-4], pos = 1 输出：true

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

输入：head = [1,2], pos = 0 输出：true

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

输入：head = [1], pos = -1 输出：false

解释：链表中没有环。

提示

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

算法

set

遍历链表，在set中判断是否有当前节点，如果有返回true，如果没有则将这个节点添加到set中，遍历到链表尾在set中仍没有相同节点返回false

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

快慢指针（Floyd判圈算法、龟兔赛跑算法）

环形链表至少需要两个节点，所以先排除空链表和只有一个节点的链表

设置慢指针slow指向head，快指针fast指向head.next(因为如果快指针也指向head的话，while的内条件语句的判断条件fast === slow永远都会为true)，循环结束条件是快指针fast或者fast.next指向null（因为while中有fast.next.next的操作，必须判断fast.next !== null），因为快指针指向链表末尾的话就说明链表不是环形链表。

在循环中快指针fast一次走两步，慢指针slow一次走一步，如果存在环形链表，快指针fast总会在某个时刻追上慢指针slow（slow === fast），此时返回true

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const hasCycle = (head) => {
	if (!head || !head.next) return false;
	let fast = head.next,
		slow = head;
	while (fast && fast.next) {
		if (fast === slow) return true;
		fast = fast.next.next;
		slow = slow.next;
	}
	return false;
};