问题描述
对于列表节点,我有以下课程:
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
).
这篇关于有关链接列表中的虚拟节点和指针的说明的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!