时间戳

首页 > 解决方案 > 在 Python 中“就地”修改链表节点

python - 在 Python 中“就地”修改链表节点

问题描述

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

LeetCode 问题：删除链表中的节点

问题：

编写一个函数来删除单链表中的一个节点（除了尾部），只允许访问该节点。

给定链表——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->None.

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

# 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

这个答案让我感到惊讶的是，输入链表与输出链表完全相同。这是输出的屏幕截图：

不正确的 deleteNode 函数的 LeetCode 输出

实际解决方案：

复杂度为 O(1)的解决方案如下所示，并带有相应的（正确的）输出。

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

正确的 deleteNode 函数的 LeetCode 输出

我的问题：

为什么会这样node.val = node.next.val并node.next = node.next.next“就地”修改链表的节点，而重新分配node对对象引用node = node.next没有影响？node

标签： pythonlinked-listsingly-linked-list

解决方案

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. 它改变了对象。

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

推荐阅读