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

Question

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

Post 1

Post 2

Post 3

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

[...] is generally not possible.

为什么通常不可能，而不仅仅是 "it's impossible"？我的问题既涉及理论本身，也涉及理论如何应用于 Python？这个问题是给 C 的。

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

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

问题如下：

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，也不是不可能：

引用一个 "list handle" 对象的函数，该对象持有对头节点的引用，可以像这样删除头节点：

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 句柄更改列表的一部分而另一个不知道您已经完成所以。）

或者，一个引用头节点和returns新头的函数也可以删除头：

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)

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

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

Python: How to delete ONLY node in a singly-linked list in O(1) time

python

linked-list

python-3.x

singly-linked-list