两个链表同时变化

Question

我知道这个问题在不同的设置中被问了很多（例如），但并不总是用非常简单的术语，我只是没有得到以前的答案。

在一个非常简单的设置中，这是我的问题：我只是不明白为什么 dummy_head 会被实现，而我似乎没有对其进行任何操作。是python属性，还是链表特有的？有人可以逐行解释发生了什么吗？

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    
        dummy_head = ListNode(0)
        other_list = dummy_head
    
        for i in range(1, 3):
            other_list.next = ListNode(i) 
            other_list = other_list.next
        
        print('dummy_head:', dummy_head)
        print('other_list', other_list)

这是我得到的输出：

dummy_head: ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 2, next: None}}}
other_list ListNode{val: 2, next: None}

感谢您的帮助！

Answer 1

当您执行 other_list = dummy_head 时，other_list 只是对 dummy_head 的引用。这不是副本。因此，当您修改 other_list 时，它也会修改 dummy_head，因为它们指向同一个对象。您必须复制 dummy_head 或创建一个新对象。您的问题涉及 Python 中的可变对象和不可变对象。解释起来有点复杂，所以你可以阅读这个 link 来理解这个概念。

https://medium.com/@meghamohan/mutable-and-immutable-side-of-python-c2145cf72747

Answer 2

运算符=用于名称绑定。

语句 dummy_head = ListNode(0) 将 name dummy_head 绑定到表达式 ListNode(0) 的 value ]. = 运算符右侧的表达式在名称绑定之前被求值。这里，表达式 ListNode(0) 被评估为 class ListNode.

的实例

下面的语句 other_list = dummy_head 是另一个名称绑定语句，将 name other_list 绑定到 value 的表达式 dummy_head。同样，在名称绑定之前，= 右侧的表达式必须求值。表达式 dummy_head 实际上是一个绑定名称，因此它被计算为绑定到该名称的值，即之前创建的 ListNode 实例。因此，在这条语句之后，这两个名称 other_list 和 dummy_head 都绑定到相同的值 - ListNode.

的实例

Answer 3

I just don't understand why the dummy_head is actualized whereas I seemingly don't do any operation on it.

实际上是对其进行操作。在循环的第一次迭代中，它的 next 属性被赋值。这有点隐藏，但第一次迭代开始于 other_list 是 dummy_head 的同义词，因此对 next 的赋值正在变异 dummy_head.

Is it a python property, or specific to linked list?

都没有。它只是创建了一个额外的节点，其目的是简化其余代码。如果不使用这样的虚拟对象，代码会是这样的：

head = None # No dummy node now
other_list = None

for i in range(1, 3):
    if other_list is None:  # We distinguish 
        head = ListNode(i)
        other_list = head
    else:
        other_list.next = ListNode(i) 
        other_list = other_list.next

return head

另请注意，像您那样打印 dummy_head 绝不是目的。这样的函数几乎总是返回 dummy_head.next 。对 dummy_head 本身没有兴趣。 dummy_head.next 对应于我在上面的替代脚本中调用的 head。

Can someone please explain what happens line by line?

可视化它可能会有所帮助：

在循环开始之前，会创建此状态 -- 请注意，两个名称都引用相同的节点。

 dummy_head
  ↓
┌───────────┐    
│ value: 0  │
│ next: None│
└───────────┘
  ↑ 
 other_list

在循环的第一次迭代中i为1，执行other_list.next = ListNode(i)。发生的第一件事是调用 ListNode(i)。这导致：

 dummy_head      (ListNode(i))
  ↓                ↓
┌───────────┐    ┌───────────┐    
│ value: 0  │    │ value: 1  │
│ next: None│    │ next: None│
└───────────┘    └───────────┘
  ↑ 
 other_list

然后将该节点的引用分配给 other_list.next。所以我们得到：

 dummy_head      
  ↓                
┌───────────┐    ┌───────────┐    
│ value: 0  │    │ value: 1  │
│ next: ───────> │ next: None│
└───────────┘    └───────────┘
  ↑ 
 other_list

第一次迭代中发生的最后一件事是赋值 other_list = other_list.next:

 dummy_head      
  ↓                
┌───────────┐    ┌───────────┐    
│ value: 0  │    │ value: 1  │
│ next: ───────> │ next: None│
└───────────┘    └───────────┘
                   ↑ 
                  other_list

循环的下一次迭代，i 为 2，将执行相同的步骤并生成：

 dummy_head      
  ↓                
┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 0  │    │ value: 1  │    │ value: 2  │
│ next: ───────> │ next: ───────> │ next: None│
└───────────┘    └───────────┘    └───────────┘
                                    ↑ 
                                   other_list

最终迭代产生：

 dummy_head      
  ↓                
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 0  │    │ value: 1  │    │ value: 2  │    │ value: 3  │
│ next: ───────> │ next: ───────> │ next: ───────> │ next: None│
└───────────┘    └───────────┘    └───────────┘    └───────────┘
                                                     ↑ 
                                                    other_list

通常这样的函数会以 return dummy_head.next 结尾，这表示 real 列表不包含虚拟节点。然后调用者将获得对该列表的引用：

┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 1  │    │ value: 2  │    │ value: 3  │
│ next: ───────> │ next: ───────> │ next: None│
└───────────┘    └───────────┘    └───────────┘

希望这能说明问题。

两个链表同时变化

Two linked lists change simultaneously

linked-list

python-3.x