Python löscht einen Knoten in der verketteten Liste, gegeben gerade Zugang zu diesem Knoten

Question

Dies ist eine LeetCode Frage, ich wusste ihre Lösung, aber wundere mich, warum mein Code nicht funktioniert.

Schreiben Sie eine Funktion zum Löschen eines Knotens (mit Ausnahme des Ends) in einer einfach verknüpften Liste, wenn nur Zugriff auf diesen Knoten besteht.

Vermeintliche die verkettete Liste 1 -> 2 -> 3 -> 4, und Sie sind den dritten Knoten mit dem Wert 3, die verknüpfte Liste soll 1 werden gegeben -> 2 -> 4 nach Ihrer Funktion

Aufruf

Auf den ersten Blick ist meine Intuition wie ein Array löschen:

Verschiebung alle Knoten eine vordere Werte, dann den Schwanz löschen, hier ist meine Implementierung und Testfall:

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) 

Aber Nach dem löschen es hat zwei 5-Wert-Knoten, der Schwanz wurde noch gehalten, kann mir bitte jemand erklären, was hier nicht stimmt?

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 

Wirklich zu schätzen jede Hilfe.

Answer 1

Sie waren fast da, aber tun viel zu viel Arbeit Verschiebung alleval Werte um einen Knoten. Sie konnten auch nicht die letzte next Referenz löschen, weshalb Sie 5 gedruckt zweimal. Ich werde Ihnen zeigen, wie Sie das Problem zuerst richtig lösen und dann den Schwanz entfernen.

Sie können in der Tat, dieses Rätsel lösen, indem nicht den Knoten zu löschen, nur durch die value auf den nächsten Wert, und die next Zeiger auf den Knoten nach dem nächsten. Und das ist alle müssen Sie tun, müssen Sie keinen der folgenden Knoten berühren. Sie würden effektiv den nächsten Knoten löschen und machen diese Knoten halten den nächsten Wert statt:

 node 
     | 
     v 
     ---------  ---------  
---> | val: va | ---> | val: vb | ---> ? 
     ---------  ---------  

 node 
     | 
     v 
     ---------  ---------  
---> | val: vb | -+ | val: vb | -> ? 
     --------- | --------- | 
        |    | 
        ---------------- 

wird also die Umsetzung ist so einfach wie:

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 

Keine Schleife erforderlich.

Zurück zu Ihrem Versuch, beachten Sie, dass die letzte Zeile in Ihrer Funktion keine Wirkung hat. node ist ein lokaler Name in Ihrer Funktion, und referenziert den Schwanz ListNode Instanz, bis Sie stattdessen auf None setzen.

Sie hattest dies:

 node 
     | 
     v 
     -----------  
---> | val: tail | ---> None 
     ----------- 

und node = None tun dies:

 node -> None 
     X 
     | 
     v 
     -----------  
---> | val: tail | ---> None 
     ----------- 

Der eingehende Referenz aus dem vorherigen Knoten noch da.

Sie würden zu verfolgen haben die ‚One-aber-last‘ Knotenreferenz und deaktivieren Sie das .next Attribut auf, das einmal getan wird Looping:

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

# clear reference to tail 
prev.next = None 

Answer 2

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

Da Sie nicht über einen Verweis zu Ihrem aktuellen Knoten können Sie ihn nicht löschen. Aber Sie haben eine Referenz zu Ihrem nächsten Knoten. Geben Sie also Ihrem aktuellen Knoten die Rolle, die Ihr nächster Knoten zuvor hatte, , und dann löscht der Garbage Collector Ihren nächsten Knoten, da es keine Refs mehr gibt, weil Sie node.next überschrieben haben.