LeetCode 141环形链表：为何版本B比版本A更高效？

问题描述 #

给定head（链表的头节点），判断链表中是否存在环。
若存在某个节点，通过持续跟随next指针可再次到达它，则链表存在环。内部用pos表示尾节点next指针连接的节点索引，注意pos不作为参数传入。
若存在环返回true，否则返回false。

示例1 #

• 输入：head = [3,2,0,-4], pos = 1
• 输出：true
• 解释：链表存在环，尾节点连接到索引为1的节点（从0开始计数）。

我在解决这个问题时，初始解法（版本A）在上述输入中超时，修改两行代码后得到版本B，解法被接受且效率更高。想搞清楚：

1. 为何版本B比版本A更快？
2. 为何变量赋值比直接使用原对象更高效？

版本A（超时解法） #

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    // 创建快指针
    let fastPointer = null;
    // 当head存在时持续循环
    while (head) {
        // 快指针移动两步
        fastPointer = head?.next?.next || null;
        // 如果快指针为null，说明无环，返回false
        if (fastPointer === null) return false;
        // 如果快慢指针指向同一节点，说明有环，返回true
        if (fastPointer === head) return true;
        // 慢指针移动一步
        head = head.next;
    }
    // 循环结束说明无环，返回false
    return false;
};   

版本B（通过解法） #

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    // 创建快指针
    let fastPointer = head; // !!!修改点1
    // 当head存在时持续循环
    while (head) {
        // 快指针移动两步 
        // !!!修改点2，修改后解法通过！！！
        fastPointer = fastPointer?.next?.next || null;
        // 如果快指针为null，说明无环，返回false
        if (fastPointer === null) return false;
        // 如果快慢指针指向同一节点，说明有环，返回true
        if (fastPointer === head) return true;
        // 慢指针移动一步
        head = head.next;
    }
    // 循环结束说明无环，返回false
    return false;
};   

问题分析 #

版本A超时的核心原因 #

版本A的逻辑完全错误，根本不是标准的「快慢指针（龟兔赛跑）」算法：

• 每次循环中，快指针不是从自身当前位置移动两步，而是重新从当前的head节点开始跳两步。
• 当链表存在环时，这种逻辑会导致无限循环：比如示例中的环是2→0→-4→2，每次head移动到环内节点后，fastPointer都会被重置为head.next.next，永远追不上head，循环永远不会终止，最终触发超时。

版本B为何正确且高效 #

版本B才是正确的快慢指针算法实现：

• 快指针初始化为head，之后每次从自己当前的位置移动两步，慢指针（即代码中不断移动的head）每次移动一步。
• 当链表有环时，快指针速度是慢指针的两倍，最终一定会在环内追上慢指针（追赶次数是有限的）；当链表无环时，快指针会先走到链表末尾（变为null），直接返回false。

关于「变量赋值比直接使用原对象更高效」的误解 #

你提到的这个结论不成立——版本B更快的核心原因是算法逻辑的正确性，和变量赋值效率无关：

• 版本A的问题在于放弃了快指针的位置追踪，完全偏离了快慢指针算法的核心逻辑，导致无限循环；
• 版本B只是让快指针持续追踪自身位置，这是算法的正确实现方式，和「变量赋值」没有直接关联。

内容的提问来源于stack exchange，提问作者Simone Anthony