Einfach verknüpfte Liste wird nicht umgekehrt, wenn Rekursion verwendet

Question

Ich habe Probleme herauszufinden, was fehlt. Ich habe einige andere Lösungen online angeschaut, und diese scheinen nicht zu funktionieren, wenn ich die Unterschiede anwende. Ich habe viel Zeit damit verbracht, zu debuggen. Hier ist mein Code:

def recurse_reverse(self, curr, level): 
    print('-' * level, 'curr:', curr.value, '| next:', curr.next.value if curr.next else curr.next) 
    if (not curr) or (not curr.next): # if there's 0 or 1 node 
     return curr 

    # p = self.recurse_reverse(curr.next, level + 1) 
    self.recurse_reverse(curr.next, level + 1) 

    print('-' * level, 'curr:', curr.value, '->', curr.next.value, '->', 
      curr.next.next.value if curr.next.next else curr.next.next) 

    curr.next.next = curr 
    # checking if pointer moved 
    print('-' * level, 'curr:', curr.value, '->', curr.next.value, '->', 
      curr.next.next.value if curr.next.next else curr.next.next) 
    # curr.next = None 
    # return p 

Die Ausgabe erhalte ich, wenn ich rufe

my_list = SinglyLinkedList() 
my_list.add_to_tail(1) 
my_list.add_to_tail(2) 
my_list.add_to_tail(3) 
my_list.add_to_tail(4) 

print(my_list._head.value) # 1 
print(my_list._head.next.value) # 2 
print(my_list._head.next.next.value) # 3 
print(my_list._head.next.next.next.value) # 4 

my_list.recurse_reverse(my_list._head, 1) 

ist dies:

- curr: 1 | next: 2 
-- curr: 2 | next: 3 
--- curr: 3 | next: 4 
---- curr: 4 | next: None 
--- curr: 3 -> 4 -> None 
--- curr: 3 -> 4 -> 3 
-- curr: 2 -> 3 -> 4 
-- curr: 2 -> 3 -> 2 
- curr: 1 -> 2 -> 3 
- curr: 1 -> 2 -> 1 

So auf jeder Ebene gedruckt wird, scheint es, dass die Zeiger korrekt bewegt werden . Wenn ich jedoch versuche, den Kopf und den Schwanz der verknüpften Liste zu drucken, rufe ich recurse_reverse an, ich bekomme 1 bzw. 3; doch, was würde ich erwarten, 4 und 1.

In vielen Lösungen Ich habe die letzte Zeile des Codes zu sehen ist, ist curr.next = None, die next Zeiger des aktuellen Knotens zu entfernen, aber wenn enthalten, dass in meinem Code, ich bekomme AttributeError: 'NoneType' object has no attribute 'value'

ich auch

p = self.recurse_reverse(curr.next, level + 1) 

und dann return p in der letzten Zeile habe versucht Einstellung, aber das funktioniert auch nicht.

Hier ist meine Implementierung:

class _LinkNode: 
    def __init__(self, value): 
     self.value = value 
     self.next = None 

class SinglyLinkedList: 
    def __init__(self): 
     self._head = None 
     self._tail = None 
     self._length = 0 

    def add_to_tail(self, value): 
     """ 
     Add a new node to the tail of the linked list. 

     Parameters 
     ---------- 
     value : int, float, string, dict, list, etc. 

     """ 
     new_node = _LinkNode(value) 

     if self._head is None: # if linked list is empty 
      self._head = new_node 

     if self._tail: # if linked list has a tail, i.e. > 1 node 
      self._tail.next = new_node 

     self._tail = new_node # regardless of current length, update tail 

     self._length += 1 

def recurse_reverse(self, curr, level): 
    # see above 

Answer 1

Es gibt zwei Probleme mit Ihrem Code. Erstens, wenn die Liste mehr als ein Element enthält, das Sie nicht austauschen _head.next, nach recurse_reverse wird es immer noch auf das zweite Element der ursprünglichen Liste zeigen und somit bilden die letzten beiden Elemente der umgekehrten Liste eine Schleife. Das zweite Problem ist, was Sie nicht tun Tauschen Sie _head und _tail irgendwo in Ihrem Code.

Hier ist ein Weg, um die Umkehrung rekursiv zu implementieren:

@staticmethod 
def reverse(prev, node): 
    # Recurse until end of the list 
    if node: 
     SinglyLinkedList.reverse(node, node.next) 
     node.next = prev 

def recurse_reverse(self): 
    # Reverse nodes 
    SinglyLinkedList.reverse(None, self._head) 

    # Swap head & tail since they are reversed now 
    self._head, self._tail = self._tail, self._head