为什么我的反向链表函数会改变全局变量链表？

Question

以下是我的代码：

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

    def __str__(self):
        return str(self.val) + " -> " + str(self.next)

def reverse_list(head: ListNode) -> ListNode:
    prev, curr  = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

linked_list = ListNode(1, ListNode(2, ListNode(3)))

打印出来时，linked_list显示为“1 -> 2 -> 3 -> None”。但是调用函数reverse_list一次后，再打印一次linked_list，好像变异了，变成了1->None。谁能解释这背后的原因？示例如下：

print(linked_list)
# 1 -> 2 -> 3 -> None
print(reverse_list(linked_list))
# 3 -> 2 -> 1 -> None
print(linked_list)
# 1 -> None

Answer 1

发生这种情况是因为 返回的节点实例 不是传递给 reverse.

的节点实例

想象一下可能会有所帮助。在 reverse 被调用，即将开始反转的时刻，我们有这样的状态：

         curr
         head                                              prev 
          ↓                                                 ↓ 
        ┌───────────┐    ┌───────────┐    ┌───────────┐
        │ value: 1  │    │ value: 2  │    │ value: 3  │
        │ next: ───────> │ next: ───────> │ next: ───────> None
        └───────────┘    └───────────┘    └───────────┘ 
          ↑
         linked_list (global)

然后当 reverse 完成它的循环时，我们有这个：

curr     head                              prev
 ↓        ↓                                 ↓
        ┌───────────┐    ┌───────────┐    ┌───────────┐
        │ value: 1  │    │ value: 2  │    │ value: 3  │
None <────── :next  │ <────── :next  │ <─────── :next │
        └───────────┘    └───────────┘    └───────────┘ 
          ↑
         linked_list (global)

reverse 然后 returns prev 参考。很明显，这个引用的节点与 linked_list 引用的节点不同。

因此，当调用 print(reverse_list(linked_list)) 时，__repr__ 方法将获取值为 3 的节点作为参数，因此能够打印 next 链之后的所有节点。

然而，当调用print(linked_list)时，__repr__方法将获取值为1的节点作为参数，当循环查找next属性时，它会找到None -- 停止打印。当您查看上面的可视化效果时，您可以看到，如果您以 linked_list 作为参考开始，则无法访问值为 2 和 3 的节点。 linked_list 引用反向列表的 tail。

“解决办法”很简单：必须捕获reverse返回的值，重新赋值给linked_list变量即可:

linked_list = reverse_list(linked_list)

执行后，您将获得以下可视化效果：

        ┌───────────┐    ┌───────────┐    ┌───────────┐
        │ value: 1  │    │ value: 2  │    │ value: 3  │
None <────── :next  │ <────── :next  │ <─────── :next │
        └───────────┘    └───────────┘    └───────────┘ 
                                            ↑
                                           linked_list (global)

因此将您的主脚本更改为：

print(linked_list)
# 1 -> 2 -> 3 -> None
linked_list = reverse_list(linked_list)
print(linked_list)
# 3 -> 2 -> 1 -> None

为什么我的反向链表函数会改变全局变量链表？

Why does my reverse linked list function mutate the global variable linkedlist?

python

oop

linked-list

mutation