单向链表部分遍历。引用虚拟节点的 before 节点与末尾的节点不同。这怎么可能

Singly Linked list partial traversal. Before node that references the dummy node is different than it at the end. How is this possible

提问人:Luke 提问时间:11/4/2023 最后编辑:Luke 更新时间:11/5/2023 访问量:37

问:

下面我有一些代码来实现一个单链表,它实现了以下内容

给定一个单链表的头部和两个左右整数,其中 left <= right,将列表的节点从左位置反转到右位置,并返回反转列表。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right){
    // represents number of the node we are on
    let dummy = new ListNode(-1,head)
    let before = dummy
   
    for (let i = 1; i < left; i++) {
        before = before.next
    }

    console.log(before) // [1,2,3,4,5]
    console.log(dummy) //  [-1,1,2,3,4,5]

    let prev = before
    let current = before.next
 
    for (let i = left; i <= right; i++) {
       
            let next = current.next
            current.next = prev
            prev = current
            current = next
    
    }
    
    before.next.next = current
    before.next = prev
    console.log("before =", before) // [1,4,3,2,5]
    console.log("dummy = ", dummy) //  [-1,1,4,3,2,5]
    return dummy.next
}

下面的代码适用于所有输入,但对我来说,为什么在底部的 before 和 dummy 变量有时是不同的,这对我来说是一个谜。例如,对于以下输入

头部 = [1,2,3,4,5] 左 = 2 右 = 4

页面底部的控制台语句如下

before = [1,4,3,2,5]
dummy = [-1,1,4,3,2,5]

据我了解,类在 javascript 中通过引用值,因此对“虚拟”或“before”对象属性的更改总是会相互更新。但是,我明白

before = before.next

会给 before 对象一个新的地址,当我们控制台 .log 之前和虚拟变量更高时,我们会看到这个地址(之前 = [1,2,3,4,5],虚拟 = [-1,1,2,3,4,5])

但让我感到困惑的是,当我们去修改和反转之前时,虚拟变量的顺序仍然被修改,尽管显然指向内存中的不同位置。我想知道为什么“虚拟”和“before”仍然在算法结束时相互跟踪,尽管在函数顶部重新分配了 before。

JavaScript 数据结构 按引用传递 singly-linked-list sentinel

评论


答: 暂无答案