Algorithmen und Datenstrukturen · Middle · Frage 26 von 75
Wie dreht man eine einfach verkettete Liste iterativ um?
let prev = null, cur = head;
while (cur) {
const next = cur.next;
// ?
}
return prev;- 1
cur = cur.next; prev.next = cur; next = prev; - 2
prev = cur.next; cur.next = null; cur = prev; - 3
cur.next = prev; prev = cur; cur = next;
Antwort zeigen
Richtige Antwort: cur.next = prev; prev = cur; cur = next;
Erklärung
Der Zeiger jedes Knotens wird auf den vorigen Knoten umgedreht, dann rücken beide Zeiger vor. next wird zuerst gesichert, sonst ginge der Rest der Liste verloren. O(n) Zeit, O(1) Speicher.