Temuduga Pengekodan: Bagaimana Anda Menggabungkan K Sorted Linked List?

Kehendak Soalan dan Konteks Berkenaan

Diberikan satu tatasusunan lists yang mengandungi kepala (head) bagi k singly linked list, gabungkan setiap nod menjadi satu senarai yang nilainya dalam tertib tidak menurun. Mana-mana senarai input mungkin kosong, nilai boleh jadi negatif atau pendua, dan jumlah keseluruhan nod merentasi semua input ialah N.

Andaikan setiap input adalah tidak berkitar (acyclic), telah diisih, dan tidak berkongsi nod dengan input lain. Pelaksanaan boleh memautkan semula nod sedia ada dan tidak boleh memperuntukkan nod pengganti bagi setiap nilai. Nilai yang sama tidak mempunyai susunan wajib merentasi senarai input yang berbeza. Kembalikan None apabila tatasusunan kosong atau setiap head ialah None. Sasarkan masa O(N log k) dan ruang bantuan O(k).

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

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

Ini ialah masalah linked-list, jadi pemilikan penunjuk (pointer) adalah sebahagian daripada kontrak. Jika pemanggil memerlukan semua senarai input kekal tidak berubah, pilihan algoritma boleh kekal sama, tetapi output mesti memperuntukkan N nod baharu dan ruang outputnya menjadi O(N).

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon menggunakan struktur yang telah diisih. Meratakan (flattening) semua nilai dan mengisihnya berfungsi, tetapi menggunakan masa O(N log N) dan storan tambahan O(N). Mengimbas semua head semasa bagi setiap nod output menggunakan sifat terisih tetapi memerlukan kos O(Nk). Jawapan yang mantap akan meneliti set kecil mana yang boleh mengandungi minimum global seterusnya.

Isyarat kedua ialah invariant frontier. Bagi setiap senarai yang belum habis, hanya nod pertama yang belum digabungkan boleh menjadi output seterusnya. Setiap nod yang lebih dalam adalah sekurang-kurangnya sama besar kerana senarai itu telah diisih. Min-heap yang memegang satu nod frontier bagi setiap senarai yang belum habis dapat mengurangkan imbasan ke atas sehingga k calon kepada penyingkiran dan penyisipan minimum ke atas heap bersaiz paling banyak k.

Isyarat ketiga ialah pembuktian dan pengiraan kompleksiti. Jawapan harus menyatakan sebab nod yang dipilih adalah minimum secara global, sebab menolak hanya penggantinya (successor) memulihkan invariant, sebab setiap nod dikeluarkan tepat sekali, dan sebab saiz heap tidak pernah melebihi bilangan senarai yang tidak kosong. Mengatakan "gunakan priority queue" tanpa hujah tersebut meninggalkan penaakulan teras tanpa penjelasan.

Isyarat keempat ialah disiplin pelaksanaan. Dalam Python, entri heap dengan keutamaan numerik yang sama tidak boleh dibiarkan sehingga membandingkan objek ListNode. Nombor jujukan yang unik bertindak sebagai pemutus seri (tie-breaker). Apabila nod digunakan semula, kod menyimpan pengganti asal sebelum menanggalkan dan menyambungkan nod tersebut, supaya awalan yang dibina mempunyai satu pemilik yang jelas dan tidak mengekalkan penunjuk sementara ke dalam senarai yang belum digabungkan.

Isyarat terakhir ialah memilih antara dua pendekatan optimum. Min-heap dan penggabungan berpasangan seimbang (balanced pairwise merging) kedua-duanya mencapai masa O(N log k). Heap menjadikan frontier eksplisit dan boleh dilanjutkan secara semula jadi kepada iterator atau strim. Divide-and-conquer menggunakan penggabungan dua senarai biasa dan boleh menggunakan ruang kerja penunjuk malar di luar tatasusunan head. Kontrak input menentukan penerangan mana yang lebih ringkas.

Soalan untuk Dijelaskan Sebelum Menjawab

• Bolehkah saya mengubah dan menggunakan semula nod input? Jika ya, pautkan semula nod tersebut dan gunakan hanya storan heap O(k). Jika tidak,

peruntukkan output dan laporkan ruang O(N) secara berasingan daripada keadaan algoritma bantuan.

• Adakah semua input telah diisih dan tidak berkitar? Algoritma yang dinyatakan bergantung pada kedua-duanya. Mengesahkan keterisihan memerlukan kos

O(N); mengesan kitaran juga mengubah kerja dan tidak sepatutnya ditambah secara senyap pada penyelesaian asas.

• Apakah yang dikira oleh k? Biarkan m menjadi bilangan senarai yang tidak kosong. Heap memegang paling banyak m, jadi batas yang

lebih tepat ialah O(N log m) untuk m >= 2, dengan kerja linear untuk sifar atau satu senarai tidak kosong.

• Adakah nilai yang sama perlu mengekalkan susunan rentas senarai? Soalan asas hanya memerlukan nilai yang diisih. Kontrak

yang stabil memerlukan susunan sumber yang ditetapkan yang dikodkan dalam kunci heap.

• Bolehkah saya menggunakan priority queue terbina dalam bahasa? Biasanya ya melainkan penemu duga menguji pelaksanaan

heap secara berasingan. Buat penjelasan sebelum meluangkan masa temuduga menulis binary heap dari awal.

• Adakah ini linked list yang terzahir sepenuhnya atau lazy iterator? Heap boleh mengendalikan kedua-duanya, tetapi versi iterator

mesti mengelak daripada memajukan sumber sehingga nilai semasanya dikeluarkan.

• Apakah yang patut berlaku kepada tatasusunan head input? Kod di bawah membiarkan entri tatasusunan tidak disentuh tetapi

menyambung semula nodnya. Jika pemanggil memerhatikan kedua-duanya, dokumentasikan pemindahan pemilikan tersebut.

Rangka Kerja Jawapan 30 Saat

"Hanya nod pertama yang belum digabungkan bagi setiap senarai terisih boleh menjadi minimum global seterusnya, jadi saya akan mengekalkan nod-nod frontier tersebut dalam min-heap. Saya mengeluarkan (pop) nod terkecil, menyambungkannya kepada hasil, kemudian memasukkan (push) hanya penggantinya yang disimpan. Invariantnya ialah heap mengandungi tepat satu frontier daripada setiap senarai yang belum habis; oleh itu nod yang dikeluarkan adalah selamat, dan memulihkan frontier sumbernya mengekalkan invariant tersebut. Setiap daripada N nod dikeluarkan sekali dan paling banyak satu pengganti dimasukkan, dengan saiz heap paling banyak k, memberikan masa O(N log k) dan ruang bantuan O(k). Saya akan menggunakan semula nod, menambah pemutus seri unik supaya nilai yang sama tidak pernah membandingkan objek nod, dan menguji input kosong, pendua, negatif, panjang tidak sama rata, dan satu senarai. Balanced pairwise merging ialah alternatif utama dengan batas masa yang sama."

Perbincangan Mendalam Langkah Demi Langkah

Mulakan dengan alternatif mudah dan kenal pasti kerja yang berulang:

Penggabungan berjujukan mudah dipandang rendah. Jika k senarai mempunyai panjang yang sama L, kerja berkembang seperti 2L + 3L + ... + kL, iaitu O(Lk²). Memandangkan N = Lk, ia bersamaan dengan O(Nk). Penggabungan berpasangan mengelakkan akumulator yang tidak seimbang dengan menggabungkan senarai secara berperingkat (pusingan), jadi setiap nod mengambil bahagian dalam paling banyak ceil(log₂ k) tahap penggabungan.

Bagi penyelesaian heap, kekalkan invariant ini sebelum setiap penyingkiran:

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.

Permulaan menyisipkan setiap head yang tidak kosong, jadi invariant itu dipenuhi. Andaikan ia sah pada permulaan sesuatu lelaran. Mana-mana nod yang belum digabungkan sama ada merupakan frontier dalam heap atau muncul selepas frontier senarainya. Memandangkan setiap input telah diisih, nod yang lebih dalam tidak boleh lebih kecil daripada frontier tersebut. Oleh itu, entri heap minimum adalah tidak lebih besar daripada mana-mana nod yang belum digabungkan dan boleh disambungkan dengan selamat.

Selepas mengeluarkan nod, hanya senarai sumbernya yang kehilangan wakil. Simpan pengganti asal nod tersebut, tanggalkan nod, sambungkannya, dan masukkan pengganti apabila ia wujud. Semua frontier sumber lain kekal sah, jadi invariant dipulihkan. Setiap lelaran mengeluarkan satu nod; selepas tepat N lelaran, setiap senarai telah habis dan heap menjadi kosong. Ini membuktikan keterisihan, kesempurnaan, dan penamatan.

Pelaksanaan Python berikut menggunakan nombor jujukan yang meningkat secara monoton sebagai medan tupel kedua. Nombor itu unik, jadi nilai yang sama tidak pernah menyebabkan perbandingan tupel sampai ke objek nod yang tidak boleh disusun.

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

Terdapat m penyisipan awal, dengan m <= k ialah bilangan senarai yang tidak kosong. Setiap nod dikeluarkan sekali, dan setiap nod kecuali ekor (tail) terakhir boleh menyebabkan satu penyisipan. Operasi heap menelan kos O(log m) sementara heap mempunyai paling banyak m entri. Bagi m >= 2, jumlah masa ialah O(N log m), yang lazimnya dinyatakan sebagai O(N log k); bagi m <= 1, traversal ialah O(N). Heap, pembilang jujukan, dummy, dan penunjuk menggunakan ruang bantuan O(m). Nod yang dikembalikan ialah nod asal, jadi ia merupakan output dan bukannya storan algoritma baharu.

Menanggalkan node.next tidak diperlukan untuk mencari pengganti kerana ia telah disimpan terlebih dahulu. Ia menjadikan pemilikan eksplisit: awalan yang digabungkan tidak pernah menunjuk sementara ke dalam senarai sumber yang belum memenangi heap. Penyambungan seterusnya menetapkan pengganti bagi tail. Algoritma ini tidak pernah mengubah nilai dan tidak pernah menyisipkan nod yang sama dua kali di bawah kontrak input tidak berkitar dan saling eksklusif (disjoint).

Jalankan ujian yang menyasarkan struktur, bukan sekadar tatasusunan laluan mudah (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 pengesahan gred pengeluaran, rekodkan juga identiti semua nod input, telusuri output dengan set yang telah dilawati (visited set), dan buktikan tiga sifat: tiada kitaran, tepat N identiti nod unik, dan nilai tidak menurun. Ini mengesan penyisipan pendua, kehilangan nod, dan kitaran penunjuk yang mungkin terlepas daripada pengesahan nilai sahaja.

Pilih balanced pairwise merging apabila penemu duga mahukan manipulasi penunjuk, priority queue tidak tersedia, atau meminimumkan storan heap adalah penting. Pilih heap apabila sumber didedahkan sebagai iterator, apabila bilangan sumber aktif berubah, atau apabila memperjelaskan mekanisme "calon global seterusnya" meningkatkan kejelasan. Kedua-duanya adalah jawapan optimum yang sah di bawah kontrak asas; nyatakan sebab bagi pilihan tersebut.

Contoh Jawapan Berkualiti Tinggi

"Saya akan menggunakan semula nod input dan mengandaikan setiap senarai telah diisih, tidak berkitar, dan saling eksklusif. Biarkan N menjadi jumlah nod dan m senarai tidak kosong. Output seterusnya hanya boleh jadi salah satu daripada m head semasa: mana-mana nod yang lebih dalam adalah sekurang-kurangnya sama besar dengan head-nya. Oleh itu, saya akan meletakkan satu head bagi setiap senarai tidak kosong ke dalam min-heap.

Invariant saya ialah heap mengandungi tepat nod pertama yang belum digabungkan daripada setiap senarai yang belum habis dan output mengandungi setiap nod yang dikeluarkan sekali dalam susunan terisih. Saya mengeluarkan minimum, menyimpan dan menanggalkan penggantinya, menyambungkan nod, dan memasukkan pengganti tersebut. Nod yang dikeluarkan adalah selamat secara global kerana setiap nod lain yang belum digabungkan berada di belakang frontier heap yang tidak lebih kecil. Memasukkan pengganti memulihkan invariant satu-frontier-bagi-setiap-senarai.

Dalam Python, entri adalah berbentuk (value, sequence, node). Nilai jujukan yang unik menghalang keutamaan yang sama daripada cuba membandingkan objek nod; ia tidak mendakwa susunan stabil merentasi senarai kerana soalan tidak memerlukannya. Setiap nod dikeluarkan sekali dan disisipkan paling banyak sekali, dengan paling banyak m entri heap. Ini mengambil masa O(N log m), biasanya ditulis sebagai O(N log k), dan ruang bantuan O(m); sifar atau satu senarai tidak kosong adalah linear.

Saya akan menguji tatasusunan kosong, semua senarai kosong, satu senarai, panjang tidak sama rata, negatif, dan nilai yang sama. Saya juga akan mengesahkan identiti nod dan ketiadaan kitaran kerana penyelesaian ini menyambung semula penunjuk. Balanced pairwise merging ialah alternatif utama: ia juga berkos O(N log k) dan hanya menggunakan primitif cantuman dua senarai, jadi saya lebih mengutamakannya jika latihan memberi penekanan kepada kod penunjuk atau tidak membenarkan heap daripada pustaka."

Kesilapan Biasa

• Ratakan dan isih serta-merta → penyelesaian mengabaikan input yang telah diisih dan menghabiskan O(N log N) ditambah

storan output → Kekalkan satu frontier bagi setiap sumber terisih.

• Imbas semua k head bagi setiap nod → pemilihan minimum menjadi O(Nk) → **Gunakan min-heap bersaiz k atau

balanced pairwise merging.**

• Gabungkan satu senarai ke dalam hasil yang sedang berkembang berulang kali → nod awal dilalui merentasi banyak

penggabungan kemudian → Gabungkan senarai dalam pusingan seimbang.

• Masukkan setiap nod ke dalam heap → saiz heap bertambah kepada N, menghasilkan kerja O(N log N) → **Hanya tolak

satu nod semasa daripada setiap sumber.**

• Simpan (value, node) dalam heap Python → nilai yang sama cuba membandingkan objek nod yang tidak boleh disusun →

Tambah pemutus seri numerik yang unik.

• Majukan sumber sebelum menyimpan penggantinya → penyambungan semula penunjuk boleh menghilangkan baki senarai →

Simpan pengganti dahulu, kemudian tanggalkan dan sambungkan.

• Mendakwa ruang O(1) kerana nod digunakan semula → heap masih memegang sehingga k entri → **Asingkan

peruntukan output daripada keadaan bantuan.**

• Hanya sahkan nilai output → kitaran, nod pendua, atau nod yang hilang boleh terlepas daripada pengesanan → **Periksa

identiti nod, bilangan, susunan, dan kebebasan kitaran.**

• Tambah pengesahan pengisihan dan kitaran tanpa penjelasan → pelaksanaan menyelesaikan kontrak yang lebih besar

dan mengubah kos → Nyatakan andaian dan tambah pengesahan hanya apabila diminta.

Soalan Susulan dan Maklum Balas

Mengapakah nilai minimum heap merupakan minimum global seterusnya?

Setiap senarai terisih yang belum habis menyumbang nod pertamanya yang belum digabungkan. Mana-mana nod lain berada di belakang salah satu daripada frontier ini dan tidak boleh lebih kecil daripadanya. Oleh itu, frontier terkecil adalah tidak lebih besar daripada setiap nod yang belum digabungkan. Mengeluarkannya adalah selamat, dan menyisipkan penggantinya memulihkan liputan bagi sumber tersebut.

Apakah yang berubah jika nilai yang sama mesti stabil mengikut susunan senarai input?

Tentukan kestabilan dengan tepat, kemudian gunakan kunci heap seperti nilai yang diikuti oleh indeks senarai sumber. Oleh kerana hanya satu nod bagi setiap sumber yang hadir, indeks sumber menyelesaikan seri rentas senarai sementara susunan dalaman setiap senarai dikekalkan secara semula jadi. Pemutus seri jujukan asas hanya menjamin kebolehbandingan, bukan dasar yang lebih ketat itu.

Bilakah divide-and-conquer lebih baik daripada heap?

Gunakan balanced pairwise merging apabila gabungan dua senarai sudah tersedia, temuduga menekankan manipulasi penunjuk, atau priority queue tidak tersedia. Setiap pusingan menyentuh setiap nod yang tinggal sekali dan terdapat O(log k) pusingan. Heap adalah lebih jelas untuk sumber lazy dan bilangan sumber aktif yang berubah-ubah.

Bagaimana jika senarai input mesti kekal tidak berubah?

Kekalkan logik pemilihan yang sama tetapi peruntukkan nod baharu bagi setiap nilai yang dikeluarkan. Masa kekal O(N log k). Keadaan pemilihan bantuan kekal O(k), manakala peruntukan output yang diperlukan ialah O(N). Nyatakan kedua-duanya dan bukannya menyembunyikan memori output di dalam dakwaan ruang.

Bagaimana jika terdapat sepuluh ribu slot senarai tetapi hanya lima yang tidak kosong?

Permulaan mengimbas k slot sekali, kemudian heap mengandungi paling banyak m = 5 entri. Masa yang tepat ialah O(k + N log m) dan ruang bantuan ialah O(m). Melaporkan hanya O(N log k) adalah selamat sebagai batas atas tetapi menyembunyikan kelebihan melangkau head yang kosong.

Bagaimanakah anda menggabungkan iterator terisih dan bukannya linked list?

Baca satu nilai daripada setiap iterator yang tidak kosong ke dalam heap bersama-sama dengan identiti sumbernya. Selepas mengeluarkan (yield) nilai minimum, majukan hanya sumber tersebut dan masukkan nilai seterusnya. Bukti frontier tidak berubah, hasilnya boleh bersifat lazy, dan memori kekal berkadaran dengan sumber aktif dan bukannya jumlah nilai.

Bolehkah kod menggunakan heapreplace selepas mengeluarkan nod yang mempunyai pengganti?

Bukan selepas operasi heappop yang berasingan, kerana punca (root) lama telah pun meninggalkan heap. Pelaksanaan boleh melihat (peek), menyimpan sumber root, dan menggantikan root dalam satu operasi apabila sumber tersebut mempunyai pengganti, tetapi cabang bagi sumber yang habis tetap wujud. Kod pop-kemudian-push yang lebih mudah adalah lebih senang dibuktikan dalam temuduga dan mempunyai batas asimptotik yang sama.

Bagaimanakah anda menguji ketepatan penunjuk selain daripada contoh?

Rakam setiap identiti nod input sebelum penggabungan. Telusuri hasil sambil menolak identiti yang berulang, kira tepat N nod, semak setiap nilai bersebelahan, dan sahkan set identiti sepadan. Hasilkan senarai terisih secara rawak dan bandingkan nilai dengan oracle flatten-and-sort yang dipercayai; oracle tersebut mengesahkan ujian, bukan kerumitan pengeluaran.