Temu Duga Pengekodan: Songsangkan Nod dalam Kumpulan-k (Reverse Nodes in k-Group)

Kehendak Soalan dan Konteks Berkaitan

Diberikan kepala (head) head bagi senarai berpaut tunggal dan satu integer positif k, songsangkan setiap kumpulan lengkap daripada k nod berturutan secara setempat (in place). Jika terdapat kurang daripada k nod yang tinggal pada bahagian akhir, kekalkan susunan asalnya. Sambung semula penunjuk nod dan bukannya menukar medan value.

Sebagai contoh, 1 → 2 → 3 → 4 → 5 menjadi 2 → 1 → 4 → 3 → 5 apabila k = 2, dan menjadi 3 → 2 → 1 → 4 → 5 apabila k = 3. Andaikan 1 ≤ k ≤ n ≤ 5000, input adalah tidak berkitar (acyclic), dan sasaran adalah masa O(n) dengan ruang tambahan O(1).

Soalan ini sesuai untuk temu duga pengekodan bagi peranan algoritma, bahagian belakang (backend), infrastruktur, dan kejuruteraan perisian am. Bahagian yang sukar bukanlah penyongsangan senarai asas. Bahagian yang sukar adalah membuktikan kumpulan lengkap wujud sebelum melakukan mutasi, memelihara titik masuk kumpulan seterusnya, menyambung semula kedua-dua sempadan, dan menunjukkan tiada nod yang hilang atau diletakkan dalam kitaran.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon memisahkan penemuan sempadan, penyongsangan segmen, dan penyambungan semula. Mula menyongsang sebelum mengetahui bahawa k nod masih berbaki menjadikan ekor yang tidak lengkap sukar dipulihkan tanpa storan tambahan. Penyelesaian yang kukuh melakukan tinjauan hadapan baca sahaja (read-only lookahead) sebelum menukar sebarang penunjuk.

Isyarat kedua ialah pemilikan penunjuk yang jelas. groupPrev berada sebelum kumpulan semasa, kth ialah nod terakhir bagi kumpulan lengkap, groupNext ialah titik masuk ke segmen berikutnya, dan kepala kumpulan lama menjadi ekor baharu. Pada akhir setiap lelaran, awalan yang telah siap mesti kekal boleh dicapai dan groupPrev.next mesti menjadi nod pertama yang belum diproses.

Isyarat ketiga ialah invarian dan bukannya kod yang dihafal. Mengasalkan prev kepada groupNext menjadikan kepala kumpulan lama menunjuk ke akhiran (suffix) apabila ia menjadi ekor. Sebaik sahaja penyongsangan selesai, hanya awalan sebelumnya yang perlu disambungkan ke kth; sambungan kumpulan-ke-akhiran sudah sedia betul.

Isyarat keempat ialah disiplin kerumitan. Setiap nod dilawati paling banyak sekali oleh tinjauan hadapan kumpulan lengkap dan sekali oleh penyongsangan, jadi jumlah keseluruhannya ialah O(n), manakala bilangan rujukan yang tetap memberikan ruang tambahan O(1). Versi rekursif mempunyai batas masa yang sama tetapi menggunakan ruang tindanan (stack space) yang berkadaran dengan bilangan kumpulan.

Soalan untuk Dijelaskan Sebelum Menjawab

• Apakah yang berlaku kepada kumpulan akhir yang lebih kecil daripada k? Ia kekal tidak berubah di sini. Sesetengah varian menyongsangkannya, yang

menghasilkan keputusan berbeza.

• Bolehkah nilai nod ditukar? Tidak. Nod mungkin membawa identiti, rujukan luaran, atau medan selain daripada nilai,

jadi pertukaran nilai bukanlah penyongsangan nod.

• Nilai k manakah yang sah? Kehendak soalan menjamin 1 ≤ k ≤ n. Fungsi yang boleh diguna semula masih boleh menolak

bukan integer atau nilai di bawah satu.

• Bolehkah input mengandungi kitaran? Kehendak soalan ini menyatakan tidak. Jika kitaran mungkin wujud, kontrak mesti menyatakan sama ada untuk

menolak atau mengubahnya; jika tidak, tinjauan hadapan mungkin tidak akan pernah selesai.

• Adakah algoritma mesti dilaksanakan secara setempat (in place)? Ya. Penggunaan tindanan (stack) adalah lebih mudah apabila ruang O(k) dibenarkan, tetapi tidak menepati sasaran ini.
• Adakah objek nod mesti diguna semula? Ya. Membina senarai baharu yang sekadar menyalin nilai melanggar kontrak.

Kerangka Jawapan 30 Saat

“Saya akan menambah satu nod dummy sebelum head dan mengekalkan groupPrev tepat sebelum kumpulan semasa. Setiap lelaran berjalan k langkah dari groupPrev untuk mencari kth. Jika gagal, saya kembali serta-merta kerana bahagian ekor belum diubah suai. Selepas menyimpan groupNext = kth.next, saya mengasalkan prev kepada groupNext dan menyongsangkan kumpulan semasa satu penunjuk pada satu masa. Ini menjadikan kepala kumpulan lama sebagai ekor baharu yang sudah pun menunjuk ke groupNext. Saya menyambungkan groupPrev.next ke kth, kemudian menggerakkan groupPrev ke kepala kumpulan lama. Setiap nod dilawati sekali untuk tinjauan hadapan dan sekali untuk penyongsangan, memberikan masa O(n) dan ruang tambahan O(1).”

Huraian Mendalam Langkah demi Langkah

Mulakan dengan nod dummy. Kepala senarai berubah apabila kumpulan pertama disongsangkan. Nod dummy menjadikan penyambungan awalan kepada kepala kumpulan baharu adalah serupa untuk kumpulan pertama dan setiap kumpulan yang berikutnya, mengelakkan pengendalian kes khas bagi kepala senarai.

Setiap lelaran terlebih dahulu melakukan tinjauan hadapan kumpulan lengkap. Bergerak tepat sebanyak k kali dari groupPrev untuk mendapatkan kth. Jika pergerakan mencapai null, kurang daripada k nod yang tinggal, jadi kembalikan dummy.next. Tinjauan hadapan belum menulis sebarang penunjuk, itulah sebabnya bahagian ekor yang tidak lengkap kekal tidak berubah secara automatik.

Pelaksanaannya adalah seperti berikut:

class ListNode {
  constructor(value, next = null) {
    this.value = value
    this.next = next
  }
}

function reverseKGroup(head, k) {
  if (!Number.isInteger(k) || k < 1) {
    throw new RangeError('k must be a positive integer')
  }

  const dummy = new ListNode(0, head)
  let groupPrev = dummy

  while (true) {
    let kth = groupPrev

    for (let step = 0; step < k; step += 1) {
      kth = kth.next
      if (kth === null) {
        return dummy.next
      }
    }

    const groupNext = kth.next
    let prev = groupNext
    let current = groupPrev.next

    while (current !== groupNext) {
      const nextNode = current.next
      current.next = prev
      prev = current
      current = nextNode
    }

    const oldGroupHead = groupPrev.next
    groupPrev.next = kth
    groupPrev = oldGroupHead
  }
}

Surih 1 → 2 → 3 → 4 → 5 dengan k = 3. Tinjauan hadapan menemui kth = 3, dan groupNext = 4 disimpan. Tetapkan prev = 4, kemudian tulis 1.next = 4, 2.next = 1, dan 3.next = 2. Nod 3 kini merupakan kepala kumpulan, manakala nod 1 ialah ekor dan sudah mencapai nod 4. Sambungkan nod dummy ke 3 dan gerakkan groupPrev ke nod 1. Tinjauan hadapan seterusnya tidak dapat menemui tiga nod, jadi ia kembali tanpa menyentuh 4 → 5.

Invarian gelung mempunyai tiga bahagian. Pada permulaan gelung, awalan sehingga groupPrev telah ditransformasikan dengan betul dalam kumpulan-kumpulan lengkap; groupPrev.next ialah nod pertama yang belum diproses; dan semua nod yang belum diproses kekal boleh dicapai dalam susunan input. Tinjauan hadapan yang gagal tidak melakukan sebarang penulisan, jadi invarian ini membuktikan secara langsung bahawa ekor yang tidak lengkap dipelihara. Tinjauan hadapan yang berjaya mengehadkan penyongsangan kepada tepat k nod, manakala groupNext memelihara titik masuk akhiran. Selepas penyambungan semula, awalan yang telah siap bertambah sebanyak satu kumpulan dan invarian dipulihkan. Setiap lelaran yang berjaya menggunakan k nod baharu, jadi algoritma akan ditamatkan.

Tinjauan hadapan dan penyongsangan masing-masing menyentuh sesuatu nod paling banyak sekali merentasi semua lelaran. Oleh itu, jumlah kerja keseluruhan adalah paling banyak kira-kira 2n lawatan nod: O(n), bukan O(nk). Nod dummy dan bilangan penunjuk tidak bertambah mengikut saiz input, jadi ruang bantuan adalah O(1).

Jika ruang tambahan dibenarkan, menolak satu kumpulan ke dalam tindanan dan meletupkannya (popping) adalah lebih mudah ditulis tetapi menggunakan ruang O(k). Penyelesaian rekursif boleh mengesahkan satu kumpulan lengkap, menyongsangkannya, dan melakukan rekursi pada bahagian akhiran, menggunakan ruang tindanan O(n / k). Versi lelaran ialah syor yang tepat untuk sasaran ruang malar. Bagi input yang kecil di mana keutamaannya adalah versi pertama yang cepat disemak, pendekatan tindanan boleh menjadi pertukaran kompromi (trade-off) yang munasabah jika dinyatakan secara eksplisit.

Ujian mesti melakukan lebih daripada sekadar membandingkan tatasusunan nilai. Simpan set rujukan nod asal, rentasi hasilnya, dan sahkan bahawa ia tidak berkitar, mempunyai bilangan nod yang sama, dan mengandungi rujukan yang sama tepat sebelum menyemak susunan. Kendalikan kes input kosong secara defensif, satu nod, k = 1, n = k, panjang yang boleh dibahagi sama rata, ekor yang tidak lengkap, nilai pendua, dan saiz maksimum. Nilai pendua amat berguna kerana ujian nilai sahaja tidak dapat membuktikan objek nod telah diguna semula.

Contoh Jawapan Berkualiti Tinggi

“Mula-mula saya akan mengesahkan bahawa kurang daripada k nod di bahagian belakang kekal mengikut susunan dan nilai tidak boleh ditukar. Keadaan lelaran saya ialah satu nod dummy ditambah dengan bilangan rujukan yang tetap. groupPrev sentiasa berada tepat sebelum kumpulan semasa. Saya berjalan k langkah daripadanya, dan jika kth tidak wujud, saya kembali sebelum menukar sebarang penunjuk ekor.

Bagi kumpulan yang lengkap, saya menyimpan groupNext. Saya mengasalkan prev kepada groupNext, kemudian menggunakan penyongsangan tiga penunjuk standard bermula dari kepala kumpulan lama sehingga mencapai groupNext. Pengasalan itu penting: apabila kepala lama menjadi ekor, next miliknya sudah pun mencapai segmen berikutnya. Selepas penyongsangan, kth ialah kepala baharu. Saya menyambungkan groupPrev.next kepadanya dan menggerakkan groupPrev ke kepala lama.

Invariannya ialah awalan yang diproses adalah betul dan bersambung, groupPrev.next ialah nod pertama yang belum diproses, dan akhiran kekal mengikut susunan input. Penyongsangan yang lengkap mengembangkan awalan; kumpulan yang tidak lengkap tidak menyebabkan sebarang penulisan, lalu mengekalkan bahagian ekor. Setiap nod dilawati paling banyak sekali untuk tinjauan hadapan dan sekali untuk penyongsangan, jadi masa adalah O(n) dan ruang tambahan adalah O(1). Saya akan mengesahkan identiti nod dan sifat tidak berkitar, bukan sekadar jujukan nilai.”

Kesilapan Biasa

• Menyongsang sebelum mengesahkan kumpulan penuh → ekor yang tidak lengkap dimutasi dan sukar dipulihkan →

lakukan tinjauan hadapan baca sahaja terlebih dahulu.

• Memulakan penyongsangan dengan prev = null → kumpulan dipisahkan buat sementara waktu daripada akhiran dan mudah tertinggal dalam keadaan

terputus → mulakan dengan prev = groupNext.

• Menyambungkan kepala kumpulan baharu sahaja → ekor baharu mungkin tidak mencapai akhiran → **pelihara groupNext dan

sahkan ekor baharu menunjuk kepadanya.**

• Mengekalkan kth sebagai pendahulu seterusnya → sempadan kumpulan seterusnya menjadi salah → **gerakkan groupPrev ke kepala

kumpulan lama.**

• Menukar nilai nod → identiti nod dan semantik medan yang dilampirkan terjejas → ubah next sahaja.
• Mendakwa ruang bantuan rekursif ialah O(1) → tindanan panggilan (call stack) membesar mengikut bilangan kumpulan → **gunakan lelaran untuk

ruang tambahan malar.**

• Menguji jujukan nilai sahaja → nod yang hilang, disalin, atau berkitar mungkin terlepas daripada dikesan → **sahkan juga identiti

rujukan, bilangan, dan sifat tidak berkitar.**

• Mendarabkan tinjauan hadapan dengan penyongsangan menjadi O(nk) → kumpulan-kumpulan adalah tak bersilang merentasi lelaran → **jumlahkan keseluruhan lawatan

bagi setiap nod.**

Soalan Susulan dan Maklum Balas

Soalan Susulan 1: Bagaimana jika kumpulan akhir yang lebih kecil daripada k juga mesti disongsangkan?

Tinjauan hadapan yang gagal tidak lagi boleh kembali serta-merta. Ia juga boleh mengira bilangan sebenar nod yang tinggal dan menyongsangkan segmen yang lebih pendek itu, atau algoritma boleh mengira panjang senarai terlebih dahulu dan menggunakan min(k, remaining) sebagai saiz kumpulan. Bahagian penamatan bagi invarian akan berubah, dan satu kes dengan n < k menjadi wajib.

Soalan Susulan 2: Bagaimanakah anda menyongsangkan kumpulan berselang-seli?

Teruskan meninjau ke hadapan mengikut kumpulan lengkap k nod dan kekalkan satu bendera Boolean. Kumpulan yang disongsangkan menggunakan logik asal; kumpulan yang dilangkau membiarkan penunjuk tidak disentuh dan memajukan groupPrev sebanyak k nod. Jelaskan peraturan ekor yang tidak lengkap sekali lagi, kerana sama ada ia dikira sebagai kumpulan yang dilangkau atau disongsangkan akan mengubah keputusannya.

Soalan Susulan 3: Bagaimanakah anda boleh membuktikan algoritma tidak mencipta kitaran?

Bukti tempatan menggunakan dua sempadan: simpan groupNext, yang berada di luar kumpulan semasa, dan songsangkan bermula daripada prev = groupNext sehingga current === groupNext. Setiap tepi yang ditulis semula menunjuk daripada nod semasa kepada pendahulu yang telah diproses atau titik masuk akhiran, tidak pernah kembali ke bahagian kumpulan semasa yang belum diproses. Ujian juga harus menjalankan semakan kitaran pantas-perlahan (fast-slow) dan menegaskan bilangan nod yang direntasi adalah sama dengan bilangan input.

Soalan Susulan 4: Apakah yang berubah untuk senarai dengan seratus juta nod?

Batas asimptotik kekal sama, tetapi rekursi mesti dielakkan, nod tidak boleh disalin, dan tingkah laku had masa tamat (timeout) serta pembatalan adalah penting untuk satu operasi yang panjang. Jika senarai berada dalam storan luaran atau merentasi pelbagai mesin, penyambungan semula penunjuk secara rawak dan kebolehlihatan atomik (atomic visibility) mendominasi masalah ini. Algoritma dalam ingatan (in-memory) tidak boleh dipindahkan secara langsung; reka letak data, sempadan transaksi, dan titik semak boleh pulih (recoverable checkpoints) mesti ditakrifkan terlebih dahulu.