Eine verkettete Liste umkehren
Kehren Sie eine einfach verkettete Liste iterativ mit drei Zeigern und rekursiv um und verfolgen Sie jeden Schritt in einem Whiteboard-ähnlichen Diagramm.
Eine verkettete Liste umkehren ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum das Umkehren von Listen unverzichtbar ist
Das Umkehren einer verketteten Liste gehört zu den am häufigsten gestellten Fragen in Coding-Interviews. Dabei wird geprüft, ob Sie Zeiger präzise manipulieren können, ohne den Überblick über Knoten zu verlieren. Varianten treten sowohl als eigenständige Aufgaben als auch als Teilschritte größerer Algorithmen auf, etwa bei der Palindromerkennung, beim Neuordnen einer Liste und beim Umkehren in k-Gruppen.
Der iterative Ansatz verwendet drei Zeiger: prev, curr und next_node. Der rekursive Ansatz stellt dieselbe Logik als Durchlauf über den Aufrufstapel dar. Beide erreichen O(n) Zeit; der iterative Ansatz benötigt O(1) Speicher.
Iteratives Umkehren mit drei Zeigern
Bei jedem Schritt des iterativen Umkehrens sichern Sie zunächst curr.next, damit der Rest der Liste nicht verloren geht. Anschließend drehen Sie curr.next um, sodass der Zeiger rückwärts auf prev zeigt, rücken prev auf curr vor und setzen curr auf den gespeicherten nächsten Knoten. Sobald curr zu None wird, endet die Schleife und prev ist der neue Head.
Ein hilfreicher Merksatz: Sichern, umkehren, vorrücken, vorrücken.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # Save
curr.next = prev # Flip
prev = curr # Advance prev
curr = next_node # Advance curr
return prev # new head
# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
print(head.val, end=' ') # 5 4 3 2 1
head = head.nextSchrittweise Ablaufverfolgung
Lassen Sie uns reverse_list auf 1 -> 2 -> 3 nachvollziehen. Zunächst prev=None, curr=1. Schritt 1: next=2 speichern, 1.next=None umkehren, prev=1, curr=2. Schritt 2: next=3 speichern, 2.next=1 umkehren, prev=2, curr=3. Schritt 3: next=None speichern, 3.next=2 umkehren, prev=3, curr=None. Die Schleife endet; geben Sie prev=3 zurück – dies ist der neue Kopf von 3 -> 2 -> 1.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_traced(head):
prev, curr = None, head
step = 0
while curr:
step += 1
next_node = curr.next
curr.next = prev
print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
prev = curr
curr = next_node
return prev
nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val) # 3Rekursive Umkehrung
Der rekursive Ansatz geht davon aus, dass reverse_list(head.next) den neuen Kopf des bereits umgekehrten Suffixes zurückgibt. Es bleibt nur, den Zeiger zwischen head und head.next umzudrehen: Setzen Sie head.next.next = head (verweisen Sie vom alten zweiten Knoten zurück auf den alten ersten) und head.next = None (trennen Sie die alte Vorwärtsverknüpfung). Der neue Kopf wird aus dem Basisfall nach oben weitergereicht.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_rec(head):
# Base case: empty or single node
if not head or not head.next:
return head
new_head = reverse_list_rec(head.next) # reverse suffix
head.next.next = head # former second node points back
head.next = None # sever forward link
return new_head
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
print(head.val, end=' ') # 4 3 2 1
head = head.nextTeilliste umkehren (LeetCode 92)
LeetCode 92 „Reverse Linked List II“ fordert Sie auf, die Teilliste von der Position left bis zur Position right (1-basiert) in einem Durchlauf umzukehren. Der entscheidende Trick besteht darin, den Knoten vor der Teilliste zu finden (verwenden Sie einen Dummy-Kopf, damit dies immer möglich ist), anschließend die Umkehrung mit drei Zeigern genau (right - left) Schritte lang durchzuführen und das umgekehrte Segment schließlich wieder mit dem umgebenden Teil der Liste zu verbinden.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseBetween(head, left, right):
dummy = ListNode(0, head)
pre = dummy
# Advance pre to node just before position 'left'
for _ in range(left - 1):
pre = pre.next
curr = pre.next
for _ in range(right - left):
next_node = curr.next
curr.next = next_node.next
next_node.next = pre.next
pre.next = next_node
return dummy.next
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
print(head.val, end=' ') # 1 4 3 2 5
head = head.nextKnoten in K-Gruppen umkehren (LeetCode 25)
LeetCode 25 „Reverse Nodes in k-Group“ kehrt jede aufeinanderfolgende Gruppe von k Knoten um. Der Ansatz: Prüfen Sie, ob noch k Knoten vorhanden sind; falls nicht, lassen Sie sie unverändert. Kehren Sie die nächsten k Knoten mit der iterativen Methode um, kehren Sie anschließend den Rest der Liste rekursiv um und verbinden Sie ihn damit. Die Zeitkomplexität bleibt O(n), bei einer Rekursionstiefe von O(n/k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseKGroup(head, k):
# Check if k nodes are available
curr, count = head, 0
while curr and count < k:
curr = curr.next
count += 1
if count < k:
return head # fewer than k nodes left, keep as-is
# Reverse k nodes
prev, curr = None, head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# head is now the tail of the reversed group
head.next = reverseKGroup(curr, k)
return prev
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
print(head.val, end=' ') # 2 1 4 3 5
head = head.nextPalindromische verkettete Liste
LeetCode 234 „Palindrome Linked List“: Prüfen Sie, ob eine verkettete Liste in O(n)-Zeit und mit O(1)-Speicher ein Palindrom ist. Vorgehensweise: Finden Sie den Mittelpunkt mit Slow-Fast-Pointern, kehren Sie die zweite Hälfte direkt in der Liste um, vergleichen Sie die beiden Hälften Knoten für Knoten und stellen Sie die Liste anschließend optional wieder her. Dabei werden zwei grundlegende Fähigkeiten miteinander verbunden: das Finden des Mittelpunkts und das Umkehren.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalindrome(head):
# Find mid
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Compare
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
def build(arr):
d = ListNode(0)
c = d
for v in arr:
c.next = ListNode(v)
c = c.next
return d.next
print(isPalindrome(build([1,2,2,1]))) # True
print(isPalindrome(build([1,2,3]))) # FalseIterativer vs. rekursiver Vergleich
Die iterative Umkehrung benötigt O(1) Speicher und wird im Allgemeinen bevorzugt. Die rekursive Umkehrung benötigt aufgrund der Aufruftiefe O(n) Stack-Speicher, was bei sehr langen Listen zu einem Stackoverflow führen kann (das Standardlimit von Python liegt bei ungefähr 1000 Rekursionsebenen).
Implementieren Sie in einem Vorstellungsgespräch zuerst die iterative Variante, um Ihr Bewusstsein für Speicherbeschränkungen zu zeigen. Erwähnen Sie anschließend die rekursive Variante als übersichtlichere Alternative, falls die Listenlänge begrenzt ist.
import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint
# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)Häufige Fehler beim Umkehren
Drei Fehler sind für fast alle Probleme beim Umkehren verantwortlich. Erstens: next nicht speichern, bevor es überschrieben wird: curr.next = prev zerstört die Vorwärtsreferenz, wenn next_node nicht zuvor gespeichert wurde. Zweitens: prev nicht zurückgeben: Am Ende der Schleife ist curr None, aber prev ist der neue Kopf. Drittens: falscher rekursiver Basisfall: Wenn not head.next vergessen wird, wird eine Liste mit nur einem Knoten nicht korrekt behandelt und verursacht einen AttributeError.
# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # BUG if omitted: lose rest of list
curr.next = prev
prev = curr
curr = next_node
return prev # BUG if you return curr: it is None
nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
print(h.val, end=' ') # 3 2 1
h = h.nextListe neu anordnen (LeetCode 143)
LeetCode 143 „Reorder List“ ordnet L0 → L1 → L2 → ... → Ln zu L0 → Ln → L1 → Ln-1 → L2 → Ln-2 in O(n)-Zeit und mit O(1)-Speicher um. Die Lösung besteht aus drei Schritten: den Mittelpunkt finden, die zweite Hälfte umkehren und die beiden Hälften ineinander verschachteln. Wer das Umkehren beherrscht, kann dieses scheinbar komplexe Problem als unkomplizierte Kombination vertrauter Werkzeuge lösen.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head):
if not head or not head.next:
return
# Find mid
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow.next
slow.next = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Interleave
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
print(h.val, end=' ') # 1 4 2 3
h = h.nextZusammenfassung: Umkehren als Baustein
Das Umkehren einer verketteten Liste ist selten das eigentliche Ziel – es ist ein Baustein. Die Palindromerkennung, das Umkehren in K-Gruppen, das Neuordnen einer Liste und das Umkehren zwischen zwei Positionen basieren alle auf demselben iterativen Drei-Zeiger-Muster. Sobald dieses Muster automatisiert ist, können Sie Ihre mentale Kapazität auf die Struktur des übergeordneten Problems konzentrieren.
Üben Sie das Umkehren, bis Sie es aus dem Gedächtnis in weniger als zwei Minuten schreiben können. Es wird in irgendeiner Form in fast jeder Vorstellungsgesprächsrunde zu verketteten Listen vorkommen.
Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Lektionsrückblick
In dieser Lektion haben Sie gelernt: Das iterative Save-Flip-Advance-Advance-Muster kehrt eine Liste in O(n)-Zeit und mit O(1)-Speicher um, der rekursive Ansatz geht davon aus, dass das Suffix bereits umgekehrt ist, und korrigiert nur die letzte Verknüpfung und das Umkehren ist ein zentraler Teilschritt bei der Palindromerkennung, beim Neuordnen einer Liste und beim Umkehren in K-Gruppen. Als Nächstes behandeln wir die Zykluserkennung mit Floyds Algorithmus.
Häufig gestellte Fragen
Ist die Lektion „Eine verkettete Liste umkehren“ kostenlos?
Ja — der vollständige Text von „Eine verkettete Liste umkehren“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Eine verkettete Liste umkehren“?
Kehren Sie eine einfach verkettete Liste iterativ mit drei Zeigern und rekursiv um und verfolgen Sie jeden Schritt in einem Whiteboard-ähnlichen Diagramm. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Eine verkettete Liste umkehren“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Node-Klasse und Listenerstellung
- Eine verkettete Liste umkehren
- Zykluserkennung mit Floyds Algorithmus
- Zusammenführen, Teilen und das n-te Element vom Ende finden