Hallo,
ich schreibe bald meine Informatik Klausur und konnte so bis jetzt fast alle Übungsblätter lösen, nur ein paar Aufgaben halten sich noch hartnäckig
Vielleicht kann sie ja jemand?
Aufgabe:
Eine verkettete Liste enthält einen Zyklus, wenn man beginnend von einem Knoten p, den next-Zeigern folgt und wieder beim Knoten p ankommt. Die Liste habe n Knoten, wobei n nicht bekannt ist.
a.
Beschreiben Sie einen Algorithmus mit der Zeitkomplexität O(n), welcher bestimmt ob eine verkettete Liste einen Zyklus enthält. Sie können O(n) extra Speicherplatz verwenden.
b.
Wiederholen Sie Aufgabe a). Benutzen Sie diesmal aber nur O(1) extra Speicherplatz. Lösungshinweis: Verwenden Sie zwei Iteratoren, die sich mit verschiedenen Geschwindigkeiten durch die Liste bewegen.
Aufgabe:
In einer einfach verketteten Liste haben Sie eine Referenz auf einen Knoten, welcher nicht der letzte Knoten der Liste ist. Beschreiben Sie einen O(1) Algorithmus der den Wert in diesem Knoten löscht und die Integrität der Liste bewahrt.
Ich bin für jeden Hinweis dankbar =)