在python中遍历带有两个指针变量的链表

Question

假设您有一个函数，它将链表中节点上的每个next值设置为在其前面val节点的节点。因此，如果链表要去2->1->4->2，那么结果链表将是2->4，因为前面4个节点超出了范围。

def solve(self, node):
head = node
curr = head
while curr:
save = curr
c = 0
while c < save.val and curr:
curr = curr.next
c = c + 1
save.next = curr
return head

我有这个函数，它通过了所有的测试用例。但是我对如何在整个函数中更新头部值感到困惑。

Head从函数开头的参数中复制一个节点开始，然后复制到curr变量中。python不都是按值传递吗?为什么传入节点的原始值不能是返回的值呢?

Answer 1

头部以复制节点开始

这是造成混淆的原因:节点没有被复制。对象的标识被分配给head，你可以把它想象成一个引用。

下面是示例代码中发生的事情的可视化:

开头是这样的:

node
↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ val: 2    │    │ val:   1  │    │ val:   4  │    │ val:   2  │
│ next: ───────> │ next: ───────> │ next: ───────> │ next:None │
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

在前两次赋值(head = node和curr = head)以及外循环第一次迭代的赋值(save = curr)之后，有:

node
head
save
curr
↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ val: 2    │    │ val:   1  │    │ val:   4  │    │ val:   2  │
│ next: ───────> │ next: ───────> │ next: ───────> │ next: ───────> None
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

内循环迭代到c == 2之后，我们得到:

node
head
save                              curr
↓                                 ↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ val: 2    │    │ val:   1  │    │ val:   4  │    │ val:   2  │
│ next: ───────> │ next: ───────> │ next: ───────> │ next: ───────> None
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

然后执行save.next = curr，这是唯一一个列表变化的语句:

node
head
save                              curr
↓           ┌────────────────┐    ↓
┌───────────┐ │  ┌───────────┐ │  ┌───────────┐    ┌───────────┐
│ val: 2    │ │  │ val:   1  │ └> │ val:   4  │    │ val:   2  │
│ next: ──────┘  │ next: ───────> │ next: ───────> │ next: ───────> None
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

外循环的下一次迭代中，再次执行save = curr:

node                              save
head                              curr
↓           ┌────────────────┐    ↓
┌───────────┐ │  ┌───────────┐ │  ┌───────────┐    ┌───────────┐
│ val: 2    │ │  │ val:   1  │ └> │ val:   4  │    │ val:   2  │
│ next: ──────┘  │ next: ───────> │ next: ───────> │ next: ───────> None
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

一旦内部循环完成，curr将变成None:

node                               
head                              save                             curr
↓           ┌────────────────┐    ↓                                ↓
┌───────────┐ │  ┌───────────┐ │  ┌───────────┐    ┌───────────┐
│ val: 2    │ │  │ val:   1  │ └> │ val:   4  │    │ val:   2  │
│ next: ──────┘  │ next: ───────> │ next: ───────> │ next: ───────> None
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

然后再次执行save.next = curr:

node                               
head                              save                             curr
↓           ┌────────────────┐    ↓           ┌────────────────┐   ↓
┌───────────┐ │  ┌───────────┐ │  ┌───────────┐ │  ┌───────────┐ │
│ val: 2    │ │  │ val:   1  │ └> │ val:   4  │ │  │ val:   2  │ └>
│ next: ──────┘  │ next: ───────> │ next: ──────┘  │ next: ───────> None
└───────────┘    └───────────┘    └───────────┘    └───────────┘ 

最后执行return head。这将返回与作为参数传递给函数(node)完全相同的引用。

注意:由于两个节点现在已经不可达，垃圾收集器可能会释放它们的内存，所以调用者将以这种状态结束:

head                              
↓                                 
┌───────────┐                     ┌───────────┐
│ val: 2    │                     │ val:   4  │
│ next: ────────────────────────> │ next: ────────────────────────> None
└───────────┘                     └───────────┘