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刪除鏈接列表中的節點，只需訪問該節點

回答

相關問題