Zusammenführen, Teilen und das n-te Element vom Ende finden
Führen Sie zwei sortierte verkettete Listen in O(n) zusammen, teilen Sie eine Liste mithilfe langsamer und schneller Zeiger am Mittelpunkt und finden Sie den n-ten Node vom Ende.
Zusammenführen, Teilen und das n-te Element vom Ende finden ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 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.
Drei grundlegende Muster für verkettete Listen
Diese Lektion behandelt drei grundlegende Operationen für verkettete Listen, die in anspruchsvolleren Problemen ständig als Bausteine vorkommen: zwei sortierte Listen zusammenführen (wird bei Merge-Sort und K-Wege-Merge verwendet), eine Liste an ihrem Mittelpunkt aufteilen (wird bei Merge-Sort und der Palindromerkennung verwendet) und den n-ten Knoten vom Ende aus finden (wird bei remove-nth-from-end verwendet).
Alle drei Operationen basieren auf Techniken, die Sie bereits kennengelernt haben: dem Dummy-Kopfknoten, Slow-Fast-Pointern und sorgfältiger Grenzverfolgung.
Zwei sortierte Listen zusammenführen
LeetCode 21 „Merge Two Sorted Lists“: Gegeben sind zwei sortierte verkettete Listen; geben Sie eine einzelne zusammengeführte sortierte Liste zurück. Verwenden Sie einen Dummy-Kopf und einen curr-Zeiger auf das Ende. Vergleichen Sie in jedem Schritt die Köpfe der beiden Listen und hängen Sie den kleineren Knoten an curr an. Wenn eine Liste erschöpft ist, hängen Sie den Rest der anderen an. Zeit: O(n+m), Speicher: O(1) (Umschreiben an Ort und Stelle).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining nodes
return dummy.next
def build(arr):
d = ListNode(); c = d
for v in arr:
c.next = ListNode(v); c = c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))Die Zusammenführung Schritt für Schritt verfolgen
Verfolgen Sie mergeTwoLists([1,2,4], [1,3,4]): 1 und 1 vergleichen – l1(1) auswählen, l1 auf 2 vorrücken. 2 und 1 vergleichen – l2(1) auswählen, l2 auf 3 vorrücken. 2 und 3 vergleichen – l1(2) auswählen, l1 auf 4 vorrücken. 4 und 3 vergleichen – l2(3) auswählen, l2 auf 4 vorrücken. 4 und 4 vergleichen – l1(4) auswählen, l1 auf None vorrücken. Den verbleibenden l2(4) anhängen. Ergebnis: [1,1,2,3,4,4].
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
step = 0
while l1 and l2:
step += 1
if l1.val <= l2.val:
print(f'Step {step}: pick l1({l1.val})')
curr.next = l1; l1 = l1.next
else:
print(f'Step {step}: pick l2({l2.val})')
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
mergeTwoLists(build([1,2,4]),build([1,3,4]))Mittelpunkt mit Slow-Fast-Pointern finden
Um eine Liste an ihrem Mittelpunkt aufzuteilen, verwenden Sie das Slow-Fast-Pointer-Muster. slow bewegt sich um 1 Position weiter, fast um 2. Wenn fast None (oder den letzten Knoten) erreicht, befindet sich slow am Mittelpunkt. Bei einer Liste gerader Länge ist dies der erste der beiden mittleren Knoten, was beim Aufteilen für Merge-Sort üblich ist.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_at_mid(head):
'''Returns (first_half_head, second_half_head).'''
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # second half starts here
slow.next = None # sever the list
return head, mid
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second)) # [1,2,3] [4,5]Mergesort für eine verkettete Liste
LeetCode 148 'Sort List': Sortieren Sie eine verkettete Liste in O(n log n) Zeit und mit O(log n) Speicherplatz. Der Ansatz: Teilen Sie die Liste am Mittelpunkt, sortieren Sie beide Hälften rekursiv und führen Sie sie zusammen. Mergesort für verkettete Listen eignet sich besonders gut, weil das Teilen am Mittelpunkt O(n) benötigt (im Gegensatz zu O(1) bei Arrays), die Gesamtkomplexität aber weiterhin O(n log n) bei nur O(log n) Speicherplatz für den Aufruf-Stack beträgt.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
# Split
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recurse
left = sortList(head)
right = sortList(mid)
# Merge
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(sortList(build([4,2,1,3])))) # [1,2,3,4]Den n-ten Knoten vom Ende finden
LeetCode 19 'Remove Nth Node From End of List': Finden Sie den n-ten Knoten vom Ende in einem einzigen Durchlauf. Verwenden Sie zwei Zeiger mit genau n Knoten Abstand. Bewegen Sie fast um n Schritte vor slow. Bewegen Sie anschließend beide gemeinsam weiter, bis fast den letzten Knoten erreicht. Zu diesem Zeitpunkt befindet sich slow am (n+1)-ten Knoten vom Ende – dem Vorgänger des zu entfernenden Knotens.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
slow = dummy
while fast: # advance both until fast is None
slow = slow.next
fast = fast.next
slow.next = slow.next.next # remove nth node
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2))) # [1,2,3,5]Warum beim Entfernen des n-ten Knotens n+1 Schritte nötig sind
Die entscheidende Feinheit besteht darin, fast um n+1 Schritte (nicht n) vom Dummy-Kopf aus weiterzubewegen. Nach n+1 Schritten ist fast slow um n+1 Positionen voraus (beide starten beim Dummy-Kopf). Wenn fast None erreicht (eine Position hinter dem Ende), befindet sich slow n+1 Positionen vor None – also an der Position (length - n - 1), wenn ab null gezählt wird, beziehungsweise am Vorgänger des Zielknotens. Dadurch kann slow.next = slow.next.next den n-ten Knoten vom Ende sauber löschen.
# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow) 1 2 3(fast) 4 5 None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')Schnittpunkt zweier verketteter Listen
LeetCode 160 'Intersection of Two Linked Lists': Finden Sie den Knoten, an dem sich zwei Listen erstmals überschneiden. Der Trick für O(1) Speicherplatz: Bewegen Sie zwei Zeiger weiter, einen pro Liste. Wenn ein Zeiger None erreicht, setzen Sie ihn auf den Kopf der jeweils anderen Liste. Nach höchstens len(A) + len(B) Schritten haben beide Zeiger dieselbe Gesamtstrecke zurückgelegt und müssen am Schnittpunkt ankommen (oder beide bei None sein, falls es keinen Schnittpunkt gibt).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a # None if no intersection
# Build: A: 4->1->\ B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val) # 8K sortierte Listen zusammenführen (Divide and Conquer)
LeetCode 23 'Merge K Sorted Lists': Gegeben seien k sortierte Listen. Führen Sie sie zu einer einzigen Liste zusammen. Der optimale Ansatz: Führen Sie mithilfe von Divide and Conquer wiederholt Listenpaare zusammen und halbieren Sie dabei in jeder Runde die Anzahl der Listen. Bei k Listen mit einer durchschnittlichen Länge n benötigt dieser Ansatz O(n k log k) Zeit statt O(n k²) beim sequenziellen Zusammenführen. Ein Min-Heap-Ansatz benötigt ebenfalls O(n k log k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
def merge_two(l1, l2):
dummy = ListNode(0); curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged.append(merge_two(l1, l2))
lists = merged
return lists[0]
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists))) # [1,1,2,3,4,4,5,6]Ungerade-gerade verkettete Liste
LeetCode 328 'Odd Even Linked List': Gruppieren Sie zuerst alle Knoten mit ungeradem Index und danach die Knoten mit geradem Index (1-basiert). Der Ansatz: Verwalten Sie zwei getrennte Ketten (ungerade und gerade) und verbinden Sie sie am Ende. Ein Durchlauf durch die Liste genügt, wodurch O(n) Zeit und O(1) Speicherplatz benötigt werden. Dies ist ein anschauliches Beispiel dafür, wie zwei Zeiger gleichzeitig mit unterschiedlichen Schrittweiten weiterbewegt werden.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(oddEvenList(build([1,2,3,4,5])))) # [1,3,5,2,4]Alles zusammenführen
Die drei Muster dieser Lektion – sortierte Listen zusammenführen, am Mittelpunkt teilen und den n-ten Knoten vom Ende finden – haben ein gemeinsames Thema: Verwenden Sie zusätzliche Zeigervariablen, um Positionen ohne zusätzlichen Speicher zu verfolgen. Der Dummy-Kopf vereinfacht das Zusammenführen und Löschen; der Abstand zwischen slow und fast legt eine bestimmte relative Position fest; das vorherige Weiterbewegen eines Zeigers erzeugt den gewünschten Abstand.
Benennen Sie in einem Vorstellungsgespräch das verwendete Muster, bevor Sie programmieren: „Ich verwende die Zwei-Zeiger-Abstandstechnik, um den n-ten Knoten vom Ende in einem Durchlauf zu finden.“ Das zeigt strukturiertes Denken.
Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Das Zusammenführen zweier sortierter Listen verwendet einen Dummy-Kopf und vergleicht bei jedem Schritt, wodurch O(n+m) Zeit und O(1) Speicherplatz benötigt werden, beim Teilen am Mittelpunkt werden Slow-Fast-Zeiger verwendet, wobei fast beim letzten gültigen Paar stoppt und beim Finden des n-ten Knotens vom Ende wird fast um n+1 Schritte vorausbewegt, sodass slow beim Vorgänger landet. Als Nächstes erstellen wir Stacks und Queues und wenden sie auf klassische Interviewprobleme an.
Häufig gestellte Fragen
Ist die Lektion „Zusammenführen, Teilen und das n-te Element vom Ende finden“ kostenlos?
Ja — der vollständige Text von „Zusammenführen, Teilen und das n-te Element vom Ende finden“ 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 „Zusammenführen, Teilen und das n-te Element vom Ende finden“?
Führen Sie zwei sortierte verkettete Listen in O(n) zusammen, teilen Sie eine Liste mithilfe langsamer und schneller Zeiger am Mittelpunkt und finden Sie den n-ten Node vom Ende. 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 4 von 4.
Wie lange dauert die Lektion „Zusammenführen, Teilen und das n-te Element vom Ende finden“?
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