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

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 值感到困惑。

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

Answer 1

Head starts with a copied node

这是混淆的原因：节点没有被复制。对象的标识分配给 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，这是唯一一个列表mutated:

的语句

 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。此 returns 与作为参数传递给函数的引用完全相同 (node)。

注意：因为两个节点现在变得不可访问，垃圾收集器可能会释放它们的内存，所以调用者将以这种状态结束：

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

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

Traversing a linked list with 2 pointer variables in python

python

linked-list