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

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)

显然，如果您将其更改为搜索一个值而不是一个节点，同样的事情会起作用。