Merge k sorted list secara berurutan bakal memproses node dari list-list sebelumnya berulang kali. Dengan jumlah list sampai 10.000, perbandingan yang berulang itu bisa mendominasi kerjanya.
Min heap dan divide and conquer mengurangi perbandingan node yang berulang di versi sequential.
Memahami Soalnya
Kita dikasih array berisi k linked list, dan setiap list udah terurut secara ascending. Tugas kita adalah merge semuanya jadi satu linked list yang terurut.
Ini batasannya:
- k == lists.length
- 0 <= k <= 10^4 (sampai 10.000 list!)
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] terurut secara ascending
- Jumlah total lists[i].length nggak akan melebihi 10^4
Contoh 1:
- Input:
lists = [[1,4,5],[1,3,4],[2,6]] - Output:
[1,1,2,3,4,4,5,6]
Contoh 2:
- Input:
lists = [] - Output:
[]
Contoh 3:
- Input:
lists = [[]] - Output:
[]
Menggabungkan satu list setiap langkah
Gabungkan dua list pertama, lalu gabungkan hasilnya dengan list ketiga, dan lanjutkan. Cara ini memakai ulang function merge dua list, tapi hasil gabungannya ditelusuri berkali-kali.
function mergeKLists(lists) {
if (!lists || lists.length === 0) return null;
// Merge two sorted lists
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}
// Merge lists one by one
let result = lists[0];
for (let i = 1; i < lists.length; i++) {
result = mergeTwoLists(result, lists[i]);
}
return result;
}
Cara ini jalan, tapi nggak efisien. Dengan k list yang masing-masing berisi n node:
Time Complexity: O(k² × n)
- Merge pertama: n + n = 2n
- Merge kedua: 2n + n = 3n
- Merge ketiga: 3n + n = 4n
- ...dan seterusnya
- Total: n + 2n + 3n + ... + kn = n(1 + 2 + 3 + ... + k) = O(k² × n)
Scan yang berulang ini mahal kalau k = 10.000.
Menggabungkan secara berpasangan
Memasangkan list menghindari penggabungan hasil yang makin besar dengan satu list kecil secara berulang. Setiap ronde menggabungkan hasil pasangan sebelumnya.
Setiap ronde mengurangi jumlah list:
- Ronde 1: Merge list[0] dengan list[1], list[2] dengan list[3], dan seterusnya.
- Ronde 2: Merge hasil dari ronde 1
- Lanjutkan sampai tersisa satu list
function mergeKLists(lists) {
if (!lists || lists.length === 0) return null;
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}
// Divide and conquer
while (lists.length > 1) {
const mergedLists = [];
for (let i = 0; i < lists.length; i += 2) {
const l1 = lists[i];
const l2 = i + 1 < lists.length ? lists[i + 1] : null;
mergedLists.push(mergeTwoLists(l1, l2));
}
lists = mergedLists;
}
return lists[0];
}
Time Complexity: O(N log k)
- Ada log k level (setiap level membagi dua jumlah list)
- Di setiap level, kita memproses total N node
- Total: O(N log k)
Space Complexity: O(k)
Setiap ronde membuat array mergedLists yang berisi head dari list. Ronde pertama menyimpan sampai ceil(k / 2) head. Kode ini memakai ulang node dari input, tapi array tambahannya tetap butuh O(k) space.
Untuk lists = [[1,4,5],[1,3,4],[2,6]], proses merge-nya berjalan seperti ini:
Ronde 1: Merge berpasangan
- Merge [1,4,5] dan [1,3,4] → [1,1,3,4,4,5]
- Merge [2,6] dan null → [2,6]
- Setelah ronde 1:
[[1,1,3,4,4,5], [2,6]]
Ronde 2: Merge berpasangan
- Merge [1,1,3,4,4,5] dan [2,6] → [1,1,2,3,4,4,5,6]
- Setelah ronde 2:
[[1,1,2,3,4,4,5,6]]
Tersisa satu list hasil merge.
Pendekatan min heap
Opsi kedua adalah min heap. Di titik mana pun, kita cuma butuh nilai terkecil di antara head saat ini dari k list.
Idenya:
- Masukkan node pertama dari setiap list ke min heap
- Ambil nilai minimum, yang jadi node berikutnya
- Kalau node itu punya node berikutnya, tambahkan ke heap
- Ulangi sampai heap kosong
function mergeKLists(lists) {
if (!lists || lists.length === 0) return null;
// Min-heap implementation using array
class MinHeap {
constructor() {
this.heap = [];
}
push(node) {
this.heap.push(node);
this.bubbleUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return min;
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index].val >= this.heap[parentIndex].val) break;
[this.heap[index], this.heap[parentIndex]] =
[this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
bubbleDown(index) {
while (true) {
let smallest = index;
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;
if (leftChild < this.heap.length &&
this.heap[leftChild].val < this.heap[smallest].val) {
smallest = leftChild;
}
if (rightChild < this.heap.length &&
this.heap[rightChild].val < this.heap[smallest].val) {
smallest = rightChild;
}
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] =
[this.heap[smallest], this.heap[index]];
index = smallest;
}
}
isEmpty() {
return this.heap.length === 0;
}
}
const heap = new MinHeap();
// Add first node from each list to heap
for (const list of lists) {
if (list) heap.push(list);
}
const dummy = new ListNode(0);
let current = dummy;
// Extract min and add next nodes
while (!heap.isEmpty()) {
const node = heap.pop();
current.next = node;
current = current.next;
if (node.next) {
heap.push(node.next);
}
}
return dummy.next;
}
Time Complexity: O(N log k) dengan N adalah jumlah total node
- Setiap node dari N node dimasukkan ke heap dan diambil dari heap sekali
- Setiap operasi heap butuh O(log k) time
- Total: O(N log k)
Space Complexity: O(k) untuk heap-nya
Untuk k = 10.000 dan N = 10.000, heap-nya melakukan kerja sebesar O(N log k), bukan O(kN) seperti di metode sequential.
Membandingkan Kedua Pendekatan
Kedua metode butuh kerja merge sebesar O(N log k) kalau k minimal dua. Keduanya juga memeriksa k head dari list input. Batas yang juga mencakup list kosong dan k = 1 adalah O(k + N log(k + 1)).
| Pendekatan | Time Complexity | Space Complexity | Kelebihan | Kekurangan |
|---|---|---|---|---|
| Divide and conquer | O(N log k) | O(k) | Merge berpasangan | Butuh array berisi head dari list |
| Min-heap | O(N log k) | O(k) | Pemrosesan bertahap | Lebih kompleks, O(k) space |
Aku lebih memilih divide and conquer di sini karena bisa memakai ulang helper merge berpasangan tanpa implementasi heap terpisah.
Min heap berguna kalau output perlu dihasilkan secara bertahap. Heap cuma menyimpan head saat ini dari setiap list.
Jebakan yang Sering Muncul
-
Pengecekan null: Selalu tangani list kosong, list null, dan list yang isinya cuma list kosong.
-
Edge case:
- Array input kosong:
lists = [] - Array dengan satu list kosong:
lists = [[]] - Array dengan campuran list kosong dan list yang nggak kosong
- Array input kosong:
-
Implementasi heap: Kalau bikin heap sendiri, pastikan perbandingannya benar (min heap pakai < bukan >).
-
Off by one error: Di divide and conquer, waktu memasangkan list, tangani jumlah list yang ganjil dengan benar.
-
Dummy node: Memakai dummy node bikin kode jauh lebih bersih. Jangan lupa return
dummy.next, bukandummy.

Memuat komentar...