为什么在改变链表中不同的节点时头部会发生变化?

Question

将cur替换为cur.next(else语句)后，当cur发生变化时，头部是如何变化的?

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur=head
while cur.val and cur.next:
if cur.val==cur.next.val:
cur.next=cur.next.next
else:            
cur=cur.next
print(cur)  
return head

我知道，当我们做cur=head时，我们正在创建一个引用，因此对头部所做的任何更改都将被更新(因为cur和head具有相同的id)，但是当进入else时，cur被更改，cur和head不再具有相同的id(在else中只有cur被更改)，但是当我们回到if子句时，cur上的任何修改也会影响头部。怎么会这样，他们甚至没有相同的身份?

Answer 1

首先，代码在while条件中不应该有cur.val。当cur.val为0时，异常是没有意义的。

现在的问题是:head不一定会改变:只有当它有一个重复的值时，它才会发生变化。无论它本身是否有重复项，如果列表中有重复项，链head引用确实改变了。因此，您可以将其解释为head被更改，但这只是"远程"更改。

它可能有助于想象它。假设我们有一个有4个节点的链表，它们的值分别是1 2 2 3。有一个重复的，所以结果列表中应该有一个节点被省略。

下面是cur=head执行时的状态，就在循环开始之前:

head  cur
│    │
┌─┴────┴────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ val:   1  │    │ val: 2    │    │ val: 2    │    │ val: 3    │
│ next: ─────────┤ next: ─────────┤ next: ─────────┤ next: None│ 
└───────────┘    └───────────┘    └───────────┘    └───────────┘

然后在循环中，将1与2进行比较，因此我们进入else块，并为cur分配另一个引用，…那是在cur.next(碰巧也是head.next)。在赋值之后，cur将引用与head.next相同的内容:

head                cur
│                  │
┌─┴─────────┐    ┌───┴───────┐    ┌───────────┐    ┌───────────┐
│ val:   1  │    │ val: 2    │    │ val: 2    │    │ val: 3    │
│ next: ─────────┤ next: ─────────┤ next: ─────────┤ next: None│ 
└───────────┘    └───────────┘    └───────────┘    └───────────┘

在第二次迭代中，if条件为真，因此发生了突变(即属性)。分配给):cur.next = cur.next.next。右边的表达式是对列表中最后一个节点的引用，并且cur节点被改变为使用其next属性引用它:

head                cur
│                  │          ┌───────────────┐
┌─┴─────────┐    ┌───┴───────┐  │ ┌───────────┐ │  ┌───────────┐
│ val:   1  │    │ val: 2    │  │ │ val: 2    │ └──┤ val: 3    │
│ next: ─────────┤ next: ───────┘ │ next: ─────────┤ next: None│ 
└───────────┘    └───────────┘    └───────────┘    └───────────┘

此时，第二个值为2的节点被分离——不再有对它的引用，因此可以对它进行垃圾收集。既然我们再也无法到达它，那么没有它，描绘这种状态也没有什么不同:

head                cur
│                  │          
┌─┴─────────┐    ┌───┴───────┐    ┌───────────┐
│ val:   1  │    │ val: 2    │    │ val: 3    │
│ next: ─────────┤ next: ─────────┤ next: None│ 
└───────────┘    └───────────┘    └───────────┘

这个突变发生在cur引用的节点上，但是因为head.next也引用了那个节点，所以这个突变可以被"看到"。通过head(通过next链)。这不是head属性的直接突变，但进一步的变化可以看到。

在下一次迭代中，cur处的值与3比较，这意味着我们进入if块，cur = cur.next使cur引用最后一个节点。注意，该语句是对名称的赋值——它不会改变任何对象。要改变对象，必须给属性赋值。

无论如何，我们得到了这样的状态:

head                                 cur
│                                   │
┌─┴─────────┐    ┌───────────┐    ┌───┴───────┐
│ val:   1  │    │ val: 2    │    │ val: 3    │
│ next: ─────────┤ next: ─────────┤ next: None│ 
└───────────┘    └───────────┘    └───────────┘

现在while条件为假，并且head返回给调用者，而名称cur现在被丢弃。所以调用者看到这个:

(returned)
│
┌─┴─────────┐    ┌───────────┐    ┌───────────┐
│ val:   1  │    │ val: 2    │    │ val: 3    │
│ next: ─────────┤ next: ─────────┤ next: None│ 
└───────────┘    └───────────┘    └───────────┘

我希望这能说清楚。