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



我已经阅读了下面的帖子,但它们没有回答我的问题。

帖子 1

帖子 2

帖子 3

这篇文章接近解释。@Rishikesh Raje 投票最多的答案是,删除单向链表中的最后一个节点是

[...]通常是不可能的。

为什么通常不可能,而不仅仅是"不可能"?我的问题既在于理论本身,也在于它如何应用于Python?这个问题是针对C的。

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

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

问题来了:

编写一个函数来删除单向链接中的节点(尾部除外( 列表,仅授予对该节点的访问权限。

假设链表是 1 -> 2 -> 3 -> 4,你会得到 第三个节点的值为 3,链表应变为 1 -> 2 -> 4 调用函数后。

我的代码可以达到所需的结果 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?请注意,这个链表只有一个节点(这意味着它是最后一个节点(,这就是传递给函数的内容。 能做到吗? 如果是这样,我应该进行哪些修改?

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

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

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


接受对包含对头节点引用的"列表句柄"对象的引用的函数可以删除头节点,如下所示:

handle.head = handle.head.next

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

*head = (*head)->next

列表句柄实际上可以像以下那样简单:

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

但通常你希望实际使用它 - 例如,添加insertdeleteappend等方法,甚至可能存储长度。(但是,请注意,此设计可能会破坏尾部共享,其中两个不同的列表具有不同的头部但相同的尾部,因为现在您可以通过一个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)

显然,如果您将其更改为搜索值而不是节点,则同样的事情有效。

相关内容

  • 没有找到相关文章

最新更新