ENDEAR
Kostenlos starten
Algorithmusgratis

Verkettete Liste umkehren

Drehe jeden next-Zeiger an Ort und Stelle um, mit drei Zeigern: prev, curr und nxt.

Zeit
O(n)
Speicher
O(1)

// Schritt für Schritt

Schritt 1 / 14
1function reverse(head) {2  let prev = null, curr = head;3  while (curr !== null) {4    const nxt = curr.next;5    curr.next = prev;6    prev = curr;7    curr = nxt;8  }9  return prev;10}
  1. nullprev
  2. 1curr
  3. 2
  4. 3
  5. 4
  6. null

prev startet bei null, curr am Kopf, 1.

So funktioniert es

Geh die Liste einmal durch. Merk dir bei jedem Knoten zuerst den nächsten, lass ihn dann auf den vorherigen zeigen und rücke beide Zeiger weiter. Wenn curr hinter das Ende fällt, ist prev der neue Kopf. O(n) Zeit und O(1) zusätzlicher Speicher.