Ich habe ein Problem mit einem Algorithmus, der verknüpfte Listen in Python rekursiv umkehrt.umgekehrt verkettete Listen rekursiv
def reverse(lis, prev = None):
if lis.next != None:
reverse(lis.next, lis)
lis.next = prev
Eingang: 3 1 4
Ausgang: 3
Jede Idee, warum arbeiten seine nicht?
Das Problem ist, dass die Wurzel der verknüpften Liste auch geändert hat: nach der Liste zu verändern, Ihr Element 3 ist in der Tat das letzte Element, Ihre Funktion eines bessere Rendite der Wurzel als auch:
def reverse(lis, prev = None):
if lis.next != None:
temp = lis.next
lis.next = prev
return reverse(temp, lis)
else:
return lis # the new root
so jetzt nennen Sie es mit:
oldroot = ... #construct linked list
newroot = reverse(oldroot)
print(newroot)
so Ihre Funktion ist richtig, aber Sie haben die falsche verknüpfte Liste Element in der Hand nach der Operation.
Dieses wie eine funktionale Programmierung Übung aussieht, so stelle ich Ihnen eine funktionale Lösung (kopiert es die Liste):
def reverse(link, rest=None):
if link is None:
return rest
return reverse(link.next, LinkedList(link.value, rest))
class LinkedList:
def __init__(self, value=None, next=None):
self.next = next
self.value = value
def print(self):
print(self.value)
if self.next is not None:
self.next.print()
def to_linked_list(items):
if len(items) == 0:
return None
return LinkedList(items[0], to_linked_list(items[1:]))
to_linked_list([1, 2, 3, 4, 5]).print()
# 1, 2, 3, 4, 5
reverse(to_linked_list([1, 2, 3, 4, 5])).print()
# 5, 4, 3, 2, 1
Schön, eine funktionelle Lösung zu präsentieren. Ein Ratschlag, den ich geben würde, besteht darin, die Funktion "__str__" außer Kraft zu setzen, anstatt die Methode ".print" zu verwenden. Aber +1! –
Anstelle stattdessen eine neue Kette zu schaffen:
def reverse_linked_list(node, prev=None):
if node.next is None:
node.next = prev
return node
root_node = reverse_linked_list(node.next, node)
node.next = prev
return root_node
@RasmiRanjanNayak Diese Frage gehört definitiv nicht zu den Codereviews, da es nicht funktioniert und die Frage nicht nach einem allgemeinen Ratschlag zur Verbesserung des Codes fragt, sondern wie man eine Fehlfunktion beheben kann. – Paul