我正在解决LeetCode问题141. Linked List Cycle:

给定head(linked list的头部),确定该linked list中是否有一个循环.

如果列表中有某个可以通过连续跟随next指针再次到达的 node ,则该列表中存在一个循环.在内部,pos用于表示tail的next指针所连接的 node 的索引.Note that 101 is not passed as a parameter.

返回true if there is a cycle in the linked list.否则,返回false.

例1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

我的原始解决方案(版本A)超出了上述输入的时间限制.我最终能够通过更改two lines of code(版本B)足够快地制定解决方案,解决方案被接受并且在某种程度上更高效.

为什么Version BVersion A快?为什么变量分配比使用原始对象更快/更有效?

我改变了这个.

版本 A ( 失效溶液 )

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    // create a fast pointer
    let fastPointer = null;
    // create a while loop that lasts for as long as head exists
    while (head) {
        // move fast pointer over by 2
        fastPointer = head?.next?.next || null;
        // if fastpointer is null, this indicates that there is no cycle so return false
        if (fastPointer === null) return false;
        // compare fastPointer to the slow pointer, if they are ever equal to the same node then the list contains a cycle.
        if (fastPointer === head) return true;
        // move head by 1
        head = head.next;
    }
    // if the while loop ends, it indicates the there is no cycle so return false
    return false;
};   

对此.

版本 B ( 工作溶液 )

var hasCycle = function(head) {
    // create a fast pointer
    let fastPointer = head; // !!!CHANGE #1
    // create a while loop that lasts for as long as head exists
    while (head) {
        // move fast pointer over by 2 
        // !!!CHANGE #2 and solution worked!!!!
        fastPointer = fastPointer?.next?.next || null;
        // if fastpointer is null, this indicates that there is no cycle so return false
        if (fastPointer === null) return false;
        // compare fastPointer to the slow pointer, if they are ever equal to the same node then the list contains a cycle.
        if (fastPointer === head) return true;
        // move head by 1
        head = head.next;
    }
    // if the while loop ends, it indicates the there is no cycle so return false
    return false;
};   

推荐答案

在故障版本中,循环有fastPointer个,由两个 node 领先,而不是head个.但这意味着fastPointer并不是真正的faster……它恰好领先两个 node ,但以与head相同的"速度"运行.您真正需要的是,fastPointer在每一步都领先increase,因此fastPointer在链接列表中是twice,而不是仅仅领先2个 node .

这也解释了为什么第一个版本达到了时间限制:当输入列表有一个循环时,它将进入无限循环,并且该循环的大小不同于2.在这种情况下,fastPointer永远不会等于head,因为它距离head正好有2个 node .例如,如果循环有3个 node ,那么fastPointer将是head之前的2个 node ,并且最终(一旦到达循环中)也是一个 node behind head.这永远不会改变:这个距离将保持不变,因此循环永远不会结束.

Javascript相关问答推荐

JavaScript:循环访问不断变化的数组中的元素

强制执行useStatego struct 化变量[foo,setFoo]的命名约定?

添加/删除时React图像上传重新渲染上传的图像

如何按预期聚合SON数据?

积分计算和 colored颜色 判断错误

如何通过在提交时工作的函数显示dom元素?

materialized - activeIndex返回-1

MongoDB中的引用

成功完成Reducers后不更新状态

在JS中拖放:检测文件

Ember.js 5.4更新会话存储时如何更新组件变量

使用ThreeJ渲染的形状具有抖动/模糊的边缘

在Matter.js中添加从点A到另一个约束的约束

如何在.NET Core中将chtml文件链接到Java脚本文件?

Reaction组件在本应被设置隐藏时仍显示

当从其他文件创建类实例时,为什么工作线程不工作?

构建器模式与参数对象输入

如何使用[ModelJSON,ArrayBuffer]调用tf.loadGraphModelSync

ComponentWillReceiveProps仍在React 18.2.0中工作

限制数组中每个元素的长度,