我已经阅读了下面的帖子,但它们没有回答我的问题。
帖子 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
但通常你希望实际使用它 - 例如,添加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)
显然,如果您将其更改为搜索值而不是节点,则同样的事情有效。