LeetCode 「简单」141.环形链表
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例
输入：head = [3,2,0,-4], pos = 1
输出：true
输入：head = [1,2], pos = 0
输出：true
输入：head = [1], pos = -1
输出：false
解答
哈希表
使用一个哈希表记录已经访问过的节点。遍历链表时，检查当前节点是否已经存在哈希表中，如果存在，则说明链表中存在环。否则，不存在环。
Code
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
const visited = new Set();
let curr = head;
while (curr) {
if (visited.has(curr)) return true;
visited.add(curr);
curr = curr.next;
}
return false;
};
快慢指针（Floyd 判圈算法）
思路
- 定义快慢指针
- 使用两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步）
- 初始化指针
- 将快指针和慢指针初始化为链表的头节点
- 移动指针
- 在链表中移动快指针和慢指针，直到快指针或慢指针的下一个节点为空（表示链表没有环）
- 如果快指针和慢指针在某个时刻相遇，说明链表中有环
- 返回结果
- 如果快指针或快指针的下一个节点为空，返回
false - 如果快指针和慢指针相遇，返回
true
Code
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
if (!head || !head.next) return false;
let fast = head, slow = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (fast === slow) return true;
}
return false;
}