有关链接列表中的虚拟节点和指针的说明

我对于列表节点具有以下类:

    def __init__(self,x):
        self.val = x
        self.next = None

如果我按以下方式初始化列表lr

l = ListNode(1)
l.next = ListNode(4)
l.next.next = ListNode(5)

r = ListNode(1)
r.next = ListNode(3)
r.next.next = ListNode(4)

# l: 1->4->5
# r: 1->3->4

,虚拟/当前节点为

dummy = cur = ListNode(0)
# cur = 0
# dummy = 0

当我设置

cur.next = l
# cur = 0->1->4->5
# dummy = 0->1->4->5

两个列表都将l放在第二个节点位置,但是当我设置时

cur = cur.next
# cur = 1->4->5
# dummy = 0->1->4->5

只有cur列表会丢失第一个节点。然后当我设置

cur.next = r
# cur = 1->1->3->4
# dummy = 0->1->1->3->4

cur列表将r列表附加在第二位置,而dummy列表将其附加在第三位置。我认为dummy看起来像0->1->3->4

我认为这是关于python中的指针或一般而言链表缺少的东西。任何解释将不胜感激!

zjd1987zjd 回答:有关链接列表中的虚拟节点和指针的说明

这里的关键是,当您将Python变量设置为对象时,它是指针,而不是值。因此,在此代码中:

dummy = cur = ListNode(0)
# cur = 0
# dummy = 0

dummycur都指向相同的对象(即相同的单元素列表)。当您将其他列表追加到cur时,您将同时将其追加到dummy,因为它是同一列表。

执行此操作时:

cur = cur.next
# cur = 1->4->5
# dummy = 0->1->4->5

您不是在创建新列表,而是在现有列表中迭代cur指针。这两个指针都是同一列表的一部分,但是dummy指向第一个元素,cur指向第二个元素。

每次调用ListNode()时,您都在创建一个新节点,因此,如果要创建两个具有相同值的节点,则需要两次调用初始化程序:

dummy = ListNode(0)
cur = ListNode(0)
# cur and dummy both have values of 0,but they're different list objects!

也:我不确定这是否是您提到“虚拟节点”时得到的结果,但是请注意,列表中没有特别需要特殊的“虚拟节点”来表示末尾。清单None可以达到这个目的(即列表的末尾是next is None的那个)。

本文链接:https://www.f2er.com/3157861.html

大家都在问