Een linked list omkeren
Keer een singly linked list iteratief om met het opnieuw verbinden van drie pointers en recursief, waarbij u elke stap volgt in een whiteboardachtig diagram.
Een linked list omkeren is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 2 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Waarom het omkeren van een gekoppelde lijst essentieel is
Het omkeren van een gekoppelde lijst behoort tot de meest gestelde programmeervragen tijdens technische sollicitatiegesprekken. Het toetst of je verwijzingen nauwkeurig kunt manipuleren zonder het overzicht over knooppunten te verliezen. Varianten komen voor als zelfstandige problemen en als deelstappen binnen grotere algoritmen, zoals palindroomdetectie, een lijst herordenen en omkeren in groepen van k.
De iteratieve aanpak gebruikt drie aanwijzers: prev, curr en next_node. De recursieve aanpak drukt dezelfde logica uit als een doorloop van de aanroepstack. Beide bereiken O(n) tijd; de iteratieve aanpak gebruikt bovendien O(1) ruimte.
Iteratief omkeren met drie aanwijzers
Bij elke stap van het iteratief omkeren doe je het volgende: sla curr.next op zodat je de rest van de lijst niet verliest, draai curr.next om zodat het naar achteren naar prev wijst, verplaats prev naar curr en verplaats curr naar de opgeslagen volgende verwijzing. Wanneer curr None wordt, eindigt de lus en is prev het nieuwe begin.
Een handig ezelsbruggetje: Opslaan, omkeren, verplaatsen, verplaatsen.
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.nextStapsgewijze doorloop
Laten we reverse_list doorlopen voor 1 -> 2 -> 3. Aanvankelijk zijn prev=None, curr=1. Stap 1: sla next=2 op, keer 1.next=None om, prev=1, curr=2. Stap 2: sla next=3 op, keer 2.next=1 om, prev=2, curr=3. Stap 3: sla next=None op, keer 3.next=2 om, prev=3, curr=None. De lus eindigt; return prev=3, de nieuwe kop van 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) # 3Recursief omkeren
De recursieve aanpak vertrouwt erop dat reverse_list(head.next) de nieuwe kop van het al omgekeerde achterste deel teruggeeft. Het enige wat nog moet gebeuren, is de pointer tussen head en head.next omkeren: stel head.next.next = head in (wijs de oude tweede knoop terug naar de oude eerste) en stel head.next = None in (verbreek de oude voorwaartse koppeling). De nieuwe kop komt vanuit het basisgeval naar boven.
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.nextEen deelijst omkeren (LeetCode 92)
LeetCode 92 'Gelinkte lijst omkeren II' vraagt je om de deelijst van positie left tot en met right om te keren, waarbij de indexering bij 1 begint, in één doorloop. De truc is om het knooppunt vóór de deelijst te vinden (gebruik een dummy-knooppunt zodat dit altijd geldig is), vervolgens de omkering met drie pointers precies (right - left) stappen uit te voeren en ten slotte het omgekeerde segment weer aan de omliggende lijst te koppelen.
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.nextKnooppunten in groepen van k omkeren (LeetCode 25)
LeetCode 25 'Knooppunten in groepen van k omkeren' keert elke opeenvolgende groep van k knooppunten om. De aanpak: controleer of er nog k knooppunten over zijn; zo niet, laat je ze ongewijzigd. Keer de volgende k knooppunten om met de iteratieve methode, keer daarna de resterende lijst recursief om en koppel die eraan vast. De tijdscomplexiteit blijft O(n), met een recursiediepte van 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.nextPalindroom in een gelinkte lijst
LeetCode 234 'Palindroom in een gelinkte lijst': controleer in O(n)-tijd en met O(1)-ruimte of een gelinkte lijst een palindroom is. Strategie: vind het middelpunt met trage en snelle pointers, keer de tweede helft ter plaatse om, vergelijk de twee helften knoop voor knoop en zet de lijst indien gewenst weer terug. Hiermee combineer je het vinden van het middelpunt en het omkeren: twee fundamentele vaardigheden.
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]))) # FalseIteratief versus recursief: vergelijking
Het iteratief omkeren gebruikt O(1) ruimte en heeft over het algemeen de voorkeur. Het recursief omkeren gebruikt O(n) stackruimte door de aanroepdiepte, wat bij zeer lange lijsten een stackoverloop kan veroorzaken (de standaardlimiet van Python is ongeveer 1000 recursieniveaus).
Implementeer tijdens een sollicitatiegesprek eerst de iteratieve versie om te laten zien dat je de ruimtebeperkingen begrijpt. Noem daarna de recursieve versie als een schoner alternatief wanneer de lengte van de lijst begrensd is.
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)Veelgemaakte fouten bij omkeren
Drie fouten veroorzaken vrijwel alle problemen bij het omkeren. Ten eerste: next niet opslaan voordat je het overschrijft: curr.next = prev vernietigt de voorwaartse verwijzing als next_node niet is opgeslagen. Ten tweede: prev niet teruggeven: aan het einde van de lus is curr None, maar prev is de nieuwe kop. Ten derde: een onjuist recursief basisgeval: als je not head.next vergeet, wordt een lijst met één knoop niet goed afgehandeld en ontstaat er een 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.nextLijst herordenen (LeetCode 143)
LeetCode 143 'Lijst herordenen' herschikt L0 → L1 → L2 → ... → Ln naar L0 → Ln → L1 → Ln-1 → L2 → Ln-2 in O(n)-tijd en met O(1)-ruimte. De oplossing combineert drie stappen: vind het middelpunt, keer de tweede helft om en verweef de twee helften. Als je omkeren beheerst, wordt dit ogenschijnlijk complexe probleem een eenvoudige combinatie van bekende hulpmiddelen.
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.nextSamenvatting: omkeren als bouwsteen
Het omkeren van een gelinkte lijst is zelden het einddoel — het is een bouwsteen. Palindroomdetectie, omkeren in groepen van k, een lijst herordenen en omkeren tussen posities maken allemaal gebruik van hetzelfde iteratieve patroon met drie pointers. Zodra je dit patroon automatisch toepast, kun je je mentale bandbreedte richten op de structuur van het probleem op een hoger niveau.
Oefen het omkeren altijd totdat je het in minder dan twee minuten uit je hoofd kunt opschrijven; het verschijnt in een of andere vorm in vrijwel elk sollicitatiegesprek over gelinkte lijsten.
Korte controle
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep in deze les.
Samenvatting van de les
In deze les heb je geleerd dat het iteratieve patroon Opslaan-Omkeren-Doorschuiven-Doorschuiven een lijst omkeert in O(n)-tijd en met O(1)-ruimte, dat de recursieve aanpak erop vertrouwt dat het achterste deel al is omgekeerd en alleen de laatste koppeling herstelt en dat omkeren een essentiële tussenstap is bij palindroomdetectie, het herordenen van een lijst en het omkeren in groepen van k. Hierna behandelen we cyclusdetectie met het algoritme van Floyd.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Een linked list omkeren” gratis?
Ja — de volledige tekst van “Een linked list omkeren” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Een linked list omkeren”?
Keer een singly linked list iteratief om met het opnieuw verbinden van drie pointers en recursief, waarbij u elke stap volgt in een whiteboardachtig diagram. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Een linked list omkeren”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Node-klasse en lijsten opbouwen
- Een linked list omkeren
- Cycli detecteren met Floyd's algoritme
- Samenvoegen, splitsen en de n-de vanaf het einde vinden