Python:如何在 O(1) 时间内删除单链表中的唯一节点

Question

我已阅读以下帖子，但它们没有回答我的问题。

Post 1

Post 2

Post 3

这个post接近于解释。 @Rishikesh Raje 投票最高的答案表示，删除单链表中的最后一个节点是

[...] is generally not possible.

为什么它通常是不可能的，而不仅仅是“这是不可能的”？我的问题既在于理论本身，又在于它如何应用于Python？这个问题是问 C 的。

此外，我的另一个问题是链表只有一个节点的情况，这也使其成为最后一个节点。

背景:我正在解决这个问题problem 在 LeetCode 上。虽然它没有要求删除最后一个案例，但我尝试了它，但由于某些我无法确定的功能，似乎无法得到它。这里的一些指导将不胜感激。我添加了一种打印值以进行调试的方法。

问题是:

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

我的代码可以达到所需的结果1 -> 2 -> 4:

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

class Solution(object):
  def deleteNode(self, node):
    """
    :type node: ListNode
    :rtype: void Do not return anything, modify node in-place instead.
    """
    nextNode = node.next

    if nextNode:
      node.val = nextNode.val
      node.next = nextNode.next
    else:
      node = None

  def listToString(self, head):
    string = ""
    while head:
      string += str(head.val) + "\n"
      head = head.next

    return string


head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

solution = Solution()
print(solution.listToString(head))
print('-'*10)
node = head.next.next
solution.deleteNode(node)
print(solution.listToString(head)) 

运行这个给我:

1
2
3
4

----------
1
2
4

但是当我将底部更改为:

head = ListNode(1)

solution = Solution()
print(solution.listToString(head))
print('-'*10)
node = head
solution.deleteNode(head)
print(solution.listToString(head))

我明白

1

----------
1

问题是: 为什么不打印 1 而不是 None？请注意，这个链表只有一个节点(这意味着它是最后一个节点)，这就是传递给函数的节点。 能做到吗？ 如果是这样，我应该做哪些修改？

Answer 1

引用列表头节点的函数可以删除头之后的任何元素，但它无法删除头。

如果你仔细想想，这应该是显而易见的。无论您做什么，您的调用者仍然对他传入的头部具有相同的引用。

但这并不是链表本身的限制，它只是 API 的限制。使用不同的 API，这并非不可能:

---

引用“列表句柄”对象的函数可以删除头节点，如下所示:

handle.head = handle.head.next

一个引用头节点引用的函数，比如 C Node **，不能直接用 Python 编写，但在可以的语言中，它就像就像使用列表句柄一样简单:

*head = (*head)->next

列表句柄实际上可以如此简单:

class LinkedList:
    def __init__(self, head=None):
        self.head = head

但通常您希望将其实际用于某些用途，例如，添加 insert、delete、append 等方法它甚至可能存储长度。 (但是，请注意，这种设计可能会破坏尾部共享，即两个不同的列表具有不同的头但相同的尾部，因为现在您可以通过一个 LinkedList 句柄更改列表的一部分，而另一个列表不知道您的情况已经这样做了。)

---

或者，引用头节点并返回新头的函数也可以删除头:

return head.next

让我们更详细地解决这个问题:

def deleteNode(head, node):
    if head == node:
        return None
    ptr = head
    while ptr and ptr.next != node:
        ptr = ptr.next
    if ptr.next == node:
        ptr.next = node.next
    return head

需要一些错误处理，但如果您遵循规则，它就会起作用:

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

# This goes from 1->2->3->4 to 1->2->4
head = deleteNode(head, head.next.next)

# And this goes to 2->4
head = deleteNode(head, head)

显然，如果您将其更改为搜索值而不是节点，则效果相同。