这是一个 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
乍一看,我的直觉是像数组一样删除:
将所有节点值移到前面,然后删除尾部,这是我的实现和测试用例:
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
def deleteNode(node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
while node.next:
node.val = node.next.val
node = node.next
node = None
deleteNode(node4)
但是删除后,它有两个5值节点,尾部仍然保留,谁能给我解释一下这里有什么问题吗?
deleteNode(node4)
node1.val
Out[162]: 1
node1.next.val
Out[163]: 2
node1.next.next.val
Out[164]: 3
node1.next.next.next.val
Out[165]: 5
node1.next.next.next.next.val
Out[166]: 5
非常感谢任何帮助。
最佳答案
您几乎完成了,但是将所有 val
值向上移动一个节点的工作量太大了。您也未能清除最后一个 next
引用,这就是为什么您看到 5
打印两次的原因。我会先告诉你如何正确地解决问题,然后再解决去除尾部的问题。
你确实可以通过不删除节点来解决这个难题,只需将value
设置为下一个值,并将next
指针到下一个之后的节点。这就是您需要做的全部,您无需触及以下任何节点。您将有效地删除下一个节点并让这个节点保存下一个值:
node
|
v
--------- ---------
---> | val: va | ---> | val: vb | ---> ?
--------- ---------
成为
node
|
v
--------- ---------
---> | val: vb | -+ | val: vb | -> ?
--------- | --------- |
| |
----------------
所以实现很简单:
def deleteNode(node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
不需要循环。
回到您的尝试,请注意您函数中的最后一行没有任何效果。 node
是您函数中的本地名称,并引用尾部 ListNode
实例,直到您将其设置为 None
代替。
你有这个:
node
|
v
-----------
---> | val: tail | ---> None
-----------
和 node = None
这样做:
node -> None
X
|
v
-----------
---> | val: tail | ---> None
-----------
来自前一个节点的传入引用仍然存在。
您必须跟踪“one-but-last”节点引用并在循环完成后清除其上的 .next
属性:
while node.next:
node.val = node.next.val
prev, node = node, node.next
# clear reference to tail
prev.next = None
关于Python删除链表中的一个节点,只要访问该节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38879291/