python - 链表中虚拟节点和指针的说明

Question

我有以下列表节点类：

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

如果我初始化列表l，r如下所示：

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 中的指针或一般链表中缺少的东西。任何解释将不胜感激！

标签： pythonpointerslinked-list

Answer 1

这里的关键是，当您将 Python 变量设置为对象时，它是一个指针，而不是一个值。所以在这段代码中：

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

dummy并且cur都指向同一个对象（即同一个单元素列表）。当您将其他列表附加到 时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很好地服务于这个目的（即列表的末尾是 who 的那个next is None）。