LeetCode链表环检测：Object实现提交失败，Set实现正常的原因排查

我在解决链表环检测问题时碰到一个问题：用普通Object实现的检测逻辑在本地测试能跑通，但提交后无法通过部分测试用例；换成Set实现相同逻辑，却能通过所有测试用例。

我的Object实现代码 #

var hasCycle = function(head) {
    let map = {};
    while(head){
        if (map[head]) return true;
        map[head] = head;
        head = head.next;
    }
    return false;
};

我的Set实现代码 #

var hasCycle = function(head) {
    let set = new Set();
    while(head){
        if (set.has(head)) return true;
        set.add(head);
        head = head.next;
    }
    return false;
};

问题出在哪？ #

普通Object的键只能是字符串或Symbol类型。当你把链表节点对象作为键存入Object时，JavaScript会自动调用对象的toString()方法，把它转成字符串。默认情况下，所有普通对象的toString()都会返回"[object Object]"。

这就导致了两个问题：

• 不同的节点对象会被当成同一个键存入Object，误判成环；
• 极端情况下，如果节点对象的toString()被重写，可能会出现相反的漏判情况。

而Set是直接存储对象的引用，判断存在性时用的是严格相等（===），不会对值做类型转换，能准确识别同一个节点对象，所以不会出错。

修复Object方案的方法 #

如果一定要用类似键值对的结构，应该用Map而不是普通Object。Map支持任意类型作为键，并且同样基于引用比较：

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

内容的提问来源于stack exchange，提问作者Yujin Dong