Overview
Zwei sortierte Listen mit Zwei-Zeiger-Technik in O(n+m) zu einer sortierten Liste zusammenführen.
Analogy
Zwei Kartenstapel, die bereits sortiert sind: immer die kleinste Karte vom Anfang beider Stapel nehmen.
Step-by-step
- Initialisiere i=0, j=0, result=[].
- Solange i<len(a) und j<len(b): füge das kleinere Element hinzu, rücke Zeiger vor.
- Füge verbleibende Elemente der nicht-leeren Liste hinzu.
Visual
a=[1,3,5], b=[2,4,6]: 1<2→[1]; 3>2→[1,2]; 3<4→[1,2,3]; 5>4→[1,2,3,4]; 5<6→[1,2,3,4,5]; +6→[1,2,3,4,5,6]
Common mistakes
- Vergessen, den Rest einer Liste anzuhängen nachdem die andere erschöpft ist.
- In-Place-Merge in einem Array erfordert sorgfältiges Indexmanagement.
Practice questions
- k sortierte Listen mit einem Min-Heap zusammenführen.
- Merge-Step in Merge-Sort implementieren.
Space
O(n+m) für Ergebnis-Liste