有关链接列表中的虚拟节点和指针的说明 [英] Explanation about dummy nodes and pointers in linked lists

问题描述

对于列表节点，我有以下课程:

I have the following class for a list node:

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

如果我按以下方式初始化列表 l 和 r :

If I initialize the lists l and r as follows:

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 放在第二个节点位置，但是当我设置时

both lists put l in the second node position, but when I set

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

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

only the cur list loses the first node. And then when I set

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

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

the cur list attaches the r list at the second position, but the dummy list attaches it at the third position. I would think dummy would look like 0->1->3->4

我认为这是我缺少的关于python中的指针或一般来说链表的东西.任何解释将不胜感激！

I figure this is something I'm missing either about pointers in python or linked lists in general. Any explanation would be appreciated!

推荐答案

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

The crucial thing here is that when you set a Python variable to an object, it's a pointer, not a value. So in this code here:

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

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

dummy and cur both point to the same object (i.e. the same single-element list). When you append your other list to cur, you're simultaneously appending it to dummy because it's the same list.

执行此操作时:

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

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

you're not creating a new list, you're just iterating your cur pointer down the existing list. Both pointers are part of the same list, but dummy points to the first element and cur points to the second element.

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

Each time you call ListNode() you're creating a new node, so if you want to create two nodes with the same value, you need to call the initializer twice:

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

---

也:我不确定这是否是您提到虚拟节点"时得到的结果，但是请注意，列表中没有特别需要特殊的虚拟节点"来表示末尾.列表; None 可以达到这个目的(即列表的末尾是 next为None 的列表).

---

Also: I'm not sure if this is what you were getting at when you mentioned "dummy nodes", but note that there is no particular need for a special "dummy node" in your list to signify the end of the list; None serves that purpose just fine (i.e. the end of the list is the one whose next is None).

这篇关于有关链接列表中的虚拟节点和指针的说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！