算法

链表循环--哈希方法

通过哈希表记录已访问过的节点，当遍历到已存在的节点时，说明存在环

链表环检测算法（LeetCode 141）

我的实现方法：哈希表检测法

原始思路

通过哈希表记录已访问过的节点，当遍历到已存在的节点时，说明存在环

初始代码

1
2
3
4
5
6
7
8
9


var hasCycle = function (head) {
    let seen = new Map()
    while(head){
        seen.set(head, true);
        head = head.next;
        if(seen.get(head)) return true
    }
    return false
};

代码优化建议

数据结构优化：Map → Set 更适合存储唯一值
逻辑顺序调整：先检查再移动指针更严谨

优化后代码

1
2
3
4
5
6
7
8
9


var hasCycle = function(head) {
    const seen = new Set();
    while (head) {
        if (seen.has(head)) return true; // 先检查当前节点
        seen.add(head);                  // 再记录访问状态
        head = head.next;                // 最后移动指针
    }
    return false;
};

问题分析

原始代码存在两个潜在风险：

检查的是head.next而非当前节点
移动指针后可能跳过最后一个节点的检查

扩展方法：快慢指针法（Floyd判圈算法）

核心思想

使用速度不同的双指针：

快指针每次走两步
慢指针每次走一步
若存在环则必然相遇

代码实现

1
2
3
4
5
6
7
8
9


var hasCycle = function(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
};

对比分析

方法	时间复杂度	空间复杂度	适用场景
哈希表检测法	O(n)	O(n)	需要记录访问路径的场景
快慢指针法	O(n)	O(1)	空间敏感型场景