Python删除链接列表中的节点，只需访问该节点

这是一个LeetCode问题，我知道它的解决方案，但想知道为什么我的代码不工作。Python删除链接列表中的节点，只需访问该节点

编写一个函数来删除单向链表中的一个节点（尾部除外），只给予该节点的访问权限。

应该链表是1 - > 2 - > 3 - > 4，你是给出值3的第三个节点，链表应该成为1 - > 2 - 呼唤你的函数后> 4

乍一看，我intution是删除就像一个数组：

转移所有的节点值一个正面，然后删除尾部，这里是我的实现和测试案例：

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

真的很感谢任何帮助。

来源

2016-08-10 XueYu

你几乎在那里，但正在做太多的工作转移全部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 
     -----------

从一个节点传入引用仍然存在。

你必须追踪“一但-最后”节点参考和清除，一旦循环完成了.next属性：

while node.next: 
    node.val = node.next.val 
    prev, node = node, node.next 

# clear reference to tail 
prev.next = None

来源

2016-08-10 16:53:09

是的，你是对的，我做了比需要更多的工作，你能看看我的代码，我认为我清理了尾巴，但尾巴仍然让我困惑。 – XueYu

@ o-o：'node = None'只设置本地名称。前面节点中的引用不受影响。 –

明白了，谢谢。 – XueYu

def deleteNode(node): 
    node.val = node.next.val 
    node.next = node.next.next

既然你没有一个参考到您当前的节点，您不能删除它。但是你有一个ref到你的下一个节点。因此，为当前节点指定您的下一个节点先前具有的角色，然后垃圾回收器将删除您的下一个节点，因为由于您覆盖了node.next而没有引用它。

来源

2016-08-10 16:54:26

Python删除链接列表中的节点，只需访问该节点

回答

相关问题