python - Python修改链表节点 "in place"

Question

我在练习一个(公认的简单的)LeetCode 问题时遇到了我的问题。但是，我真正的问题是关于 Python，而不是问题本身的答案。您将在下面看到完整的问题陈述，之后我会解释我的方法，将其与实际解决方案进行对比，然后(最后)提出我的问题。

---

LeetCode 问题:Delete Node in Linked List

问题:

编写一个函数来删除单向链表中的一个节点(尾部除外)，只允许访问该节点。

给定链表 -- head = [4,5,1,9]，如下所示:

示例 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

示例 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

注意:

• 链表至少有两个元素。
• 所有节点的值都是唯一的。
• 给定的节点不会是尾部，它永远是链表的有效节点。
• 不要从你的函数返回任何东西。

---

我的方法:

我给出了一个快速答案(在 O(n) 时是次优的，但这不是重点)我通过将已删除节点和所有节点的值全部向左移动一个单位来将它们重新分配到它的右边.在此示例中，接下来将重新分配括号中的节点:

1. 4->[5]->1->9->None 变为
2. 4->1->[1]->9->None，然后
3. 4->1->9->[9]->None，最后
4. 4->1->9->无。

或者至少，这是我对下面编写的代码的预期。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        while node != None:
            node = node.next

这个答案让我吃惊的是输入链表和输出链表完全一样。这是输出的屏幕截图:

---

实际解决方案:

solution ，具有 O(1) 的复杂性，如下所示以及相应的(正确的)输出。

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

---

我的问题:

为什么 node.val = node.next.val 和 node.next = node.next.next 会“原地”修改链表的节点"，在 node = node.next 中重新分配 node 对对象 node 引用没有影响？

Answer 1

node = node.next 只是重新分配了 deleteNode 的参数，这不会影响函数之外的任何东西。

这样想:你希望它修改 x 吗？

x = 1

def f(a):
    a = 2

f(x)

不会的。 a 只是f 内部的局部引用。它所做的所有重新分配都是更改 a 指向的对象。

比较一下:

x = []

def f(a):
    a.append(2)

f(x)

这将改变x。在这里，您不是在重新分配本地引用，而是在改变本地引用指向的对象。使用您的第二个代码，node.val = node.next.val 更改 node 内的字段。它改变了对象。

这就是您的两段代码之间的区别。第一段代码只是改变了对对象的引用。第二段代码改变了对象本身。