关于链表中的虚拟节点和指针的说明 [英] 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屋！