Wawancara Koding: Bagaimana Cara Menggabungkan K Sorted Linked List?

Konteks Soal dan Penerapannya

Diberikan sebuah array lists yang berisi kepala (head) dari k singly linked list, gabungkan setiap simpul menjadi satu list yang nilainya terurut secara non-decreasing. List input apa pun mungkin kosong, nilai dapat berupa bilangan negatif atau duplikat, dan jumlah total simpul di seluruh input adalah N.

Asumsikan setiap input bersifat asiklik, sudah terurut, dan tidak berbagi simpul dengan input lain. Implementasi boleh menautkan ulang simpul yang ada dan tidak boleh mengalokasikan simpul pengganti untuk setiap nilai. Nilai yang sama tidak memiliki urutan wajib di antara list input yang berbeda. Kembalikan None jika array kosong atau setiap head bernilai None. Targetkan waktu O(N log k) dan ruang bantu O(k).

Input:
  1 -> 4 -> 5
  1 -> 3 -> 4
  2 -> 6

Output:
  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Ini adalah masalah linked-list, sehingga kepemilikan pointer adalah bagian dari kontrak. Jika pemanggil mengharuskan semua list input tetap tidak berubah, pilihan algoritmik dapat tetap sama, tetapi output harus mengalokasikan N simpul baru dan ruang output-nya menjadi O(N).

Apa yang Dievaluasi oleh Pewawancara

Sinyal pertama adalah apakah kandidat memanfaatkan struktur yang sudah terurut. Meratakan (flattening) semua nilai dan mengurutkannya memang berhasil, tetapi menghabiskan waktu O(N log N) dan penyimpanan tambahan O(N). Memindai semua head saat ini untuk setiap simpul output memanfaatkan sifat terurut tetapi membutuhkan biaya O(Nk). Jawaban yang kuat akan menanyakan himpunan kecil mana yang dapat memuat nilai minimum global berikutnya.

Sinyal kedua adalah invarian frontier. Untuk setiap list yang belum habis, hanya simpul pertama yang belum digabungkan yang dapat menjadi output berikutnya. Setiap simpul yang lebih dalam setidaknya bernilai sama besar karena list tersebut terurut. Oleh karena itu, min-heap yang menyimpan satu simpul frontier per list yang belum habis mereduksi pemindaian hingga k kandidat menjadi penghapusan dan penyisipan minimum pada heap berukuran paling banyak k.

Sinyal ketiga adalah pembuktian dan perhitungan kompleksitas. Jawaban harus menyatakan mengapa simpul yang dipilih adalah minimum secara global, mengapa hanya memasukkan penerusnya (successor) yang memulihkan invarian, mengapa setiap simpul dikeluarkan tepat satu kali, dan mengapa ukuran heap tidak pernah melebihi jumlah list yang tidak kosong. Mengatakan "gunakan priority queue" tanpa argumen tersebut membuat penalaran inti tidak terjelaskan.

Sinyal keempat adalah kedisiplinan implementasi. Di Python, entri heap dengan prioritas numerik yang sama tidak boleh sampai membandingkan objek ListNode. Nomor urut yang unik menyediakan pemecah seri (tie-breaker). Ketika simpul digunakan kembali, kode menyimpan penerus aslinya sebelum melepaskan dan menambahkan simpul tersebut, sehingga prefiks yang dibangun memiliki satu pemilik yang jelas dan tidak mempertahankan pointer sementara ke dalam list yang belum digabungkan.

Sinyal terakhir adalah memilih di antara dua pendekatan optimal. Min-heap dan penggabungan berpasangan seimbang (balanced pairwise merging) keduanya mencapai waktu O(N log k). Heap membuat frontier menjadi eksplisit dan dapat diperluas secara alami ke iterator atau stream. Divide-and-conquer menggunakan penggabungan dua list biasa dan dapat menggunakan ruang kerja pointer konstan di luar array head. Kontrak input menentukan penjelasan mana yang lebih sederhana.

Pertanyaan untuk Diklarifikasi Sebelum Menjawab

• Bolehkah saya memutasi dan menggunakan kembali simpul input? Jika ya, tautkan kembali simpul tersebut dan gunakan hanya penyimpanan heap O(k). Jika tidak,

alokasikan output dan laporkan ruang O(N) secara terpisah dari state algoritma bantu.

• Apakah semua input terurut dan asiklik? Algoritma yang dinyatakan bergantung pada keduanya. Memvalidasi keterurutan membutuhkan biaya

O(N); mendeteksi siklus juga mengubah beban kerja dan tidak boleh ditambahkan secara diam-diam ke solusi dasar.

• Apa yang dihitung oleh k? Misalkan m adalah jumlah list yang tidak kosong. Heap menampung paling banyak m, sehingga batasan yang

lebih tepat adalah O(N log m) untuk m >= 2, dengan kerja linier untuk nol atau satu list yang tidak kosong.

• Haruskah nilai yang sama mempertahankan urutan lintas list? Pertanyaan dasar hanya membutuhkan nilai yang terurut. Kontrak

yang stabil membutuhkan urutan sumber yang terdefinisi yang dikodekan dalam kunci heap.

• Dapatkah saya menggunakan priority queue bawaan bahasa? Biasanya ya, kecuali jika pewawancara sedang menguji implementasi

heap secara terpisah. Klarifikasi sebelum menghabiskan waktu wawancara untuk menulis binary heap dari awal.

• Apakah ini linked list yang terwujud penuh (fully materialized) atau lazy iterator? Heap dapat menangani keduanya, tetapi versi iterator

harus menghindari memajukan sumber sampai nilai saat ini diambil.

• Apa yang harus terjadi pada array head input? Kode di bawah ini membiarkan entri array tidak tersentuh tetapi

menata ulang simpul-simpulnya. Jika pemanggil mengamati keduanya, dokumentasikan transfer kepemilikan tersebut.

Kerangka Jawaban 30 Detik

"Hanya simpul pertama yang belum digabungkan dari setiap list terurut yang dapat menjadi minimum global berikutnya, jadi saya akan menyimpan simpul-simpul frontier tersebut dalam min-heap. Saya mengambil (pop) simpul terkecil, menambahkannya ke hasil, lalu memasukkan (push) hanya penerusnya yang telah disimpan. Invariannya adalah heap berisi tepat satu frontier dari setiap list yang belum habis; oleh karena itu simpul yang diambil aman, dan memulihkan frontier sumbernya mempertahankan invarian tersebut. Masing-masing dari N simpul di-pop sekali dan paling banyak satu penerus di-push, dengan ukuran heap paling banyak k, menghasilkan waktu O(N log k) dan ruang bantu O(k). Saya akan menggunakan kembali simpul, menambahkan tie-breaker unik sehingga nilai yang sama tidak pernah membandingkan objek simpul, dan menguji input kosong, duplikat, nilai negatif, panjang yang tidak sama, dan satu list. Balanced pairwise merging adalah alternatif utama dengan batasan waktu yang sama."

Pembahasan Mendalam Langkah Demi Langkah

Mulailah dengan alternatif yang mudah dan identifikasi pekerjaan yang berulang:

Penggabungan sekuensial mudah diremehkan. Jika k list memiliki panjang yang serupa L, pekerjaannya tumbuh seperti 2L + 3L + ... + kL, yaitu O(Lk²). Karena N = Lk, itu adalah O(Nk). Pairwise merging menghindari akumulator yang tidak seimbang dengan menggabungkan list dalam putaran (round), sehingga setiap simpul berpartisipasi dalam paling banyak ceil(log₂ k) level penggabungan.

Untuk solusi heap, pertahankan invarian ini sebelum setiap penghapusan:

For each non-exhausted input list:
  the heap contains exactly its first unmerged node.

For each exhausted input list:
  the heap contains no node from that list.

The result contains every previously removed node exactly once,
in non-decreasing order.

Inisialisasi menyisipkan setiap head yang tidak kosong, sehingga invarian terpenuhi. Misalkan invarian ini berlaku pada awal suatu iterasi. Setiap simpul yang belum digabungkan adalah frontier di heap atau muncul setelah frontier list-nya. Karena setiap input terurut, simpul yang lebih dalam tidak mungkin lebih kecil dari frontier tersebut. Oleh karena itu, entri heap minimum tidak lebih besar dari simpul mana pun yang belum digabungkan dan dapat ditambahkan dengan aman.

Setelah menghapus simpul, hanya list sumbernya yang kehilangan perwakilannya. Simpan penerus asli simpul tersebut, lepaskan simpulnya, tambahkan ke hasil, dan masukkan penerusnya jika ada. Semua frontier sumber lainnya tetap valid, sehingga invarian dipulihkan. Setiap iterasi mengeluarkan satu simpul; setelah tepat N iterasi, setiap list habis dan heap kosong. Ini membuktikan keterurutan, kelengkapan, dan terminasi.

Implementasi Python berikut menggunakan nomor urut yang meningkat secara monoton sebagai field tupel kedua. Angka tersebut unik, sehingga nilai yang sama tidak pernah menyebabkan perbandingan tupel mencapai objek simpul yang tidak dapat diurutkan.

from __future__ import annotations

from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count


@dataclass
class ListNode:
    val: int
    next: ListNode | None = None


def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    heap: list[tuple[int, int, ListNode]] = []
    sequence = count()

    for head in lists:
        if head is not None:
            heappush(heap, (head.val, next(sequence), head))

    dummy = ListNode(0)
    tail = dummy

    while heap:
        _, _, node = heappop(heap)
        next_node = node.next
        node.next = None
        tail.next = node
        tail = node

        if next_node is not None:
            heappush(heap, (next_node.val, next(sequence), next_node))

    return dummy.next

Ada m penyisipan awal, di mana m <= k adalah jumlah list yang tidak kosong. Setiap simpul dihapus sekali, dan setiap simpul kecuali ekor (tail) terakhir dapat menyebabkan satu penyisipan. Operasi heap bernilai O(log m) sementara heap memiliki paling banyak m entri. Untuk m >= 2, total waktu adalah O(N log m), yang secara konvensional dinyatakan sebagai O(N log k); untuk m <= 1, traversal adalah O(N). Heap, sequence counter, dummy, dan pointer menggunakan ruang bantu O(m). Simpul yang dikembalikan adalah simpul asli, sehingga merupakan output dan bukan penyimpanan algoritmik baru.

Melepaskan node.next tidak diperlukan untuk menemukan penerusnya karena sudah disimpan terlebih dahulu. Ini membuat kepemilikan menjadi eksplisit: prefiks yang digabungkan tidak pernah menunjuk sementara ke list sumber yang belum memenangkan heap. Penambahan berikutnya menetapkan penerus dari tail. Algoritma tidak pernah mengubah nilai dan tidak pernah menyisipkan simpul yang sama dua kali di bawah kontrak input yang asiklik dan saling lepas (disjoint).

Jalankan pengujian yang menargetkan struktur, bukan hanya array kasus umum (happy-path):

def build(values: list[int]) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def values(head: ListNode | None) -> list[int]:
    result: list[int] = []
    while head is not None:
        result.append(head.val)
        head = head.next
    return result


cases = [
    ([], []),
    ([[]], []),
    ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
    ([[], [-3, -1, 2], [], [-3, 7]], [-3, -3, -1, 2, 7]),
    ([[5]], [5]),
]

for raw_lists, expected in cases:
    actual = values(merge_k_lists([build(items) for items in raw_lists]))
    assert actual == expected, (raw_lists, expected, actual)

Untuk validasi tingkat produksi, catat juga identitas semua simpul input, telusuri output dengan visited set, dan buktikan tiga properti: tidak ada siklus, tepat N identitas simpul unik, dan nilai-nilai yang non-decreasing. Ini menangkap penyisipan duplikat, kehilangan simpul, dan siklus pointer yang dapat terlewatkan oleh asersi yang hanya memeriksa nilai.

Pilih balanced pairwise merging ketika pewawancara menginginkan manipulasi pointer, priority queue tidak tersedia, atau meminimalkan penyimpanan heap menjadi hal yang penting. Pilih heap ketika sumber diekspos sebagai iterator, ketika jumlah sumber aktif berubah, atau ketika memperjelas mekanisme "kandidat global berikutnya" dapat meningkatkan kejelasan. Keduanya merupakan jawaban optimal yang valid di bawah kontrak dasar; sebutkan alasan pemilihannya.

Contoh Jawaban Berkualitas Tinggi

"Saya akan menggunakan kembali simpul input dan mengasumsikan setiap list terurut, asiklik, dan saling lepas. Misalkan N adalah total simpul dan m adalah list yang tidak kosong. Output berikutnya hanya bisa salah satu dari m head saat ini: simpul yang lebih dalam bernilai setidaknya sebesar head-nya. Oleh karena itu, saya akan menempatkan satu head per list yang tidak kosong ke dalam min-heap.

Invarian saya adalah bahwa heap berisi tepat simpul pertama yang belum digabungkan dari setiap list yang belum habis dan output berisi setiap simpul yang di-pop sekali dalam urutan terurut. Saya menghapus nilai minimum, menyimpan dan melepaskan penerusnya, menambahkan simpul tersebut, dan melakukan push pada penerus tersebut. Simpul yang dihapus aman secara global karena setiap simpul lain yang belum digabungkan berada di belakang frontier heap yang tidak lebih kecil. Melakukan push pada penerus memulihkan invarian satu-frontier-per-list.

Di Python, entri berupa (value, sequence, node). Nilai urutan yang unik mencegah prioritas yang sama mencoba membandingkan objek simpul; ini tidak mengklaim urutan stabil lintas list karena soal tidak memerlukannya. Setiap simpul di-pop sekali dan dimasukkan paling banyak sekali, dengan paling banyak m entri heap. Kompleksitasnya adalah O(N log m), biasanya ditulis O(N log k), dan ruang bantu O(m); nol atau satu list yang tidak kosong adalah linier.

Saya akan menguji array kosong, semua list kosong, satu list, panjang yang tidak sama, nilai negatif, dan nilai yang sama. Saya juga akan memverifikasi identitas simpul dan ketiadaan siklus karena solusinya menata ulang pointer. Balanced pairwise merging adalah alternatif utama: ia juga membutuhkan biaya O(N log k) dan hanya menggunakan primitif penggabungan dua list, sehingga saya akan lebih memilihnya jika latihan ini menekankan kode pointer atau melarang heap pustaka."

Kesalahan Umum

• Meratakan dan mengurutkan secara langsung → solusi mengabaikan input yang sudah terurut dan menghabiskan O(N log N) ditambah

penyimpanan output → Pertahankan satu frontier per sumber terurut.

• Memindai semua k head untuk setiap simpul → pemilihan minimum menjadi O(Nk) → **Gunakan min-heap berukuran k atau

balanced pairwise merging.**

• Menggabungkan satu list ke dalam hasil yang bertambah secara berulang → simpul-simpul awal dilintasi di banyak

penggabungan berikutnya → Gabungkan list dalam putaran yang seimbang.

• Memasukkan setiap simpul ke dalam heap → ukuran heap membengkak menjadi N, menghasilkan pekerjaan O(N log N) → **Hanya masukkan

satu simpul saat ini dari setiap sumber.**

• Menyimpan (value, node) dalam heap Python → nilai yang sama mencoba membandingkan objek simpul yang tidak dapat diurutkan →

Tambahkan pemecah seri numerik yang unik.

• Memajukan sumber sebelum menyimpan penerusnya → penataan ulang pointer dapat menghilangkan sisa list →

Simpan penerus terlebih dahulu, lalu lepaskan dan tambahkan.

• Mengklaim ruang O(1) karena simpul digunakan kembali → heap masih menampung hingga k entri → **Pisahkan

alokasi output dari state bantu.**

• Hanya memvalidasi nilai output → siklus, simpul duplikat, atau simpul yang hilang dapat luput dari deteksi → **Periksa

identitas simpul, jumlah, urutan, dan kebebasan dari siklus.**

• Menambahkan validasi pengurutan dan siklus tanpa klarifikasi → implementasi menyelesaikan kontrak yang lebih besar

dan mengubah biaya → Nyatakan asumsi dan tambahkan validasi hanya jika diminta.

Pertanyaan Lanjutan dan Tanggapannya

Mengapa nilai minimum pada heap merupakan nilai minimum global berikutnya?

Setiap list terurut yang belum habis menyumbangkan simpul pertamanya yang belum digabungkan. Simpul lainnya berada di belakang salah satu dari frontier ini dan tidak mungkin lebih kecil darinya. Oleh karena itu, frontier terkecil tidak lebih besar dari setiap simpul yang belum digabungkan. Menghapusnya aman, dan menyisipkan penerusnya akan memulihkan cakupan dari sumber tersebut.

Apa yang berubah jika nilai yang sama harus stabil berdasarkan urutan list input?

Definisikan kestabilan secara tepat, lalu gunakan kunci heap seperti nilai yang diikuti oleh indeks list sumber. Karena hanya satu simpul per sumber yang ada, indeks sumber menyelesaikan seri lintas list sementara urutan internal masing-masing list tetap terjaga secara alami. Sequence tie-breaker dasar hanya menjamin keterbandingan, bukan kebijakan yang lebih ketat tersebut.

Kapan divide-and-conquer lebih baik daripada heap?

Gunakan balanced pairwise merging jika penggabungan dua list sudah tersedia, wawancara menekankan manipulasi pointer, atau priority queue tidak tersedia. Setiap putaran menyentuh setiap simpul yang tersisa satu kali dan ada O(log k) putaran. Heap lebih jelas untuk sumber yang bersifat lazy dan jumlah sumber aktif yang berubah-ubah.

Bagaimana jika list input harus tetap tidak berubah?

Gunakan logika pemilihan yang sama tetapi alokasikan simpul baru untuk setiap nilai yang diambil. Waktu tetap O(N log k). State pemilihan bantu tetap O(k), sedangkan alokasi output yang diperlukan adalah O(N). Sebutkan keduanya alih-alih menyembunyikan memori output di dalam klaim ruang.

Bagaimana jika ada sepuluh ribu slot list tetapi hanya lima yang tidak kosong?

Inisialisasi memindai k slot sekali, kemudian heap memuat paling banyak m = 5 entri. Waktu yang tepat adalah O(k + N log m) dan ruang bantu adalah O(m). Melaporkan hanya O(N log k) aman sebagai batas atas tetapi menyembunyikan manfaat dari melewatkan head yang kosong.

Bagaimana Anda menggabungkan sorted iterator alih-alih linked list?

Baca satu nilai dari setiap iterator yang tidak kosong ke dalam heap bersama dengan identitas sumbernya. Setelah menghasilkan (yield) nilai minimum, majukan hanya sumber tersebut dan masukkan nilai berikutnya. Pembuktian frontier tidak berubah, hasilnya dapat bersifat lazy, dan memori tetap proporsional terhadap sumber aktif, bukan total nilai.

Bisakah kode menggunakan heapreplace setelah menghapus simpul yang memiliki penerus?

Tidak setelah pemanggilan heappop yang terpisah, karena root lama telah meninggalkan heap. Implementasi dapat melakukan peek, menyimpan sumber root, dan mengganti root dalam satu operasi ketika sumber tersebut memiliki penerus, tetapi percabangan untuk sumber yang habis tetap ada. Kode pop-lalu-push yang lebih sederhana lebih mudah dibuktikan dalam wawancara dan memiliki batasan asimtotik yang sama.

Bagaimana Anda menguji kebenaran pointer di luar contoh kasus?

Catat setiap identitas simpul input sebelum penggabungan. Telusuri hasilnya sambil menolak identitas yang berulang, hitung tepat N simpul, periksa setiap nilai yang berdekatan, dan pastikan himpunan identitas cocok. Hasilkan list terurut secara acak dan bandingkan nilainya dengan oracle flatten-and-sort yang tepercaya; oracle tersebut memverifikasi pengujian, bukan kompleksitas produksi.