K sıralı listeyi birleştir

Problem

Her biri artan sırada olan k adet bağlı liste veriliyor (bazıları boş olabilir). Hepsini tek bir artan sıralı bağlı listede birleştir ve başını döndür. Mevcut düğümleri yeniden bağlaman yeterli; yeni düğüm oluşturman gerekmiyor.

Girdi:  [ 2->6->9,  1->6,  null,  3->4->10 ]
Çıktı:  1->2->3->4->6->6->9->10

Girdi:  []
Çıktı:  null

Netleştirme soruları

• k ve toplam düğüm sayısı N ne kadar? (k = 10⁴, N = 10⁴ gibi; k'nın büyüklüğü yaklaşım seçimini etkiler.)
• Listeler boş olabilir mi, dizinin kendisi boş olabilir mi?
• Tekrar eden değerler var mı? Kararlılık (eşit değerlerde liste sırası) önemli mi?
• Mevcut düğümleri değiştirebilir miyim?
• Değer aralığı? (Comparator'ı çıkarma ile yazarken taşma riski.)

İpuçları

Yaklaşım

Brute force 1, hepsini topla ve sırala: Tüm değerleri bir diziye at, sırala, yeni liste kur. O(N log N) zaman, O(N) ek bellek. Düşündüğünden kötü değil, ama girdinin sıralı olmasından yararlanmıyor.

Brute force 2, her adımda k başı tara: Her düğüm için k başı karşılaştır. O(N × k).

Brute force 3, sırayla birleştir: Sonuca birinci listeyi, sonra ikinciyi, sonra üçüncüyü birleştir. i. birleştirmede sonuç listesi büyüdüğü için toplam O(N × k) (listeler eşit boyluysa yaklaşık k²/2 × N/k).

Optimal 1, min-heap: Heap'te her boş olmayan listenin o anki baş düğümü durur; heap boyutu hiçbir zaman k'yı geçmez. Her adımda en küçüğü poll et, sonuca bağla, onun next'ini offer et. N düğümün her biri heap'e bir kez girer, bir kez çıkar: O(N log k).

Neden doğru: heap'teki en küçük eleman, tüm listelerde henüz eklenmemiş en küçük elemandır, çünkü her liste sıralı ve listenin henüz eklenmemiş en küçüğü onun başıdır.

Optimal 2, divide and conquer: Listeleri ikişerli eşleştirip birleştir (k → k/2 → k/4 ...). log k tur, her turda toplam N düğüm işlenir: O(N log k) zaman, ek bellek O(1) (iteratif yazılırsa). Heap'e göre sabit çarpanı genelde daha düşüktür; merge sort'un birleştirme aşamasıyla aynı fikir.

Comparator tuzağı: (a, b) -> a.val - b.val yazmak, Integer.MIN_VALUE ve pozitif bir değer karşılaştırıldığında taşar ve yanlış sıra verir. Comparator.comparingInt(node -> node.val) ya da Integer.compare güvenlidir; testte uç değerlerle bu durum denendi.

Java çözümü

import java.util.Comparator;
import java.util.PriorityQueue;

public final class MergeKSortedLists {

    static final class ListNode {
        int val;
        ListNode next;

        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        // Heap'te her listenin o anki en küçük (baş) düğümü durur: en fazla k eleman
        PriorityQueue<ListNode> heads = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
        for (ListNode head : lists) {
            if (head != null) {
                heads.offer(head);
            }
        }
        ListNode dummy = new ListNode(0);                          // sentinel: "ilk düğüm mü?" kontrolü yok
        ListNode tail = dummy;
        while (!heads.isEmpty()) {
            ListNode smallest = heads.poll();
            tail.next = smallest;
            tail = smallest;
            if (smallest.next != null) {
                heads.offer(smallest.next);                        // aynı listenin sıradaki düğümü yarışa girer
            }
        }
        return dummy.next;
    }
}

Karmaşıklık

• Zaman: O(N log k). N kez poll ve en fazla N kez offer, her biri O(log k). Başlangıçta heap'e k ekleme O(k log k), N'nin içinde kalır (boş listeler hariç k ≤ N).
• Bellek: O(k) heap için. Sonuç listesi mevcut düğümlerden kurulduğu için ek düğüm yok.
• PriorityQueue kararlı değildir: eşit değerli düğümlerin liste sırası korunmaz. Gerekirse comparator'a liste index'i eklenir.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; ayrıca 2.000 rastgele girdide (0-5 liste, her biri 0-5 düğüm, negatif ve tekrarlı değerler) tüm değerleri toplayıp sıralayan referans ile karşılaştırıldı.

Mülakatçı için

"Zor" etiketine rağmen bu soru, doğru veri yapısını seçme ve karmaşıklığı k ve N ile ayrı ayrı ifade etme becerisini ölçer. Adayın birden fazla yaklaşımı (sırala, sırayla birleştir, heap, divide and conquer) karşılaştırması güçlü bir sinyaldir. Karmaşıklığı "O(n log n)" diye belirsiz söyleyen adaya "n ne?" diye sor.

İpucu zamanlaması: Aday "hepsini topla, sırala" ile başlarsa kabul et; "girdinin sıralı olmasından yararlanabilir misin?" diye sor. Sırayla birleştirmeyi önerirse karmaşıklığını hesaplatmak iyi bir egzersiz: çoğu aday O(N) sanır. Heap'e tüm düğümleri baştan atan aday O(N log N) ve O(N) bellek harcar; "heap'te aynı anda kaç düğüm olması yeterli?" diye sor.

Takip soruları:

1. Listeler bellekte değil, k ayrı dosyada (ya da k ayrı servisten gelen sıralı stream'de) duruyor ve hepsi belleğe sığmıyor. (Beklenen: aynı heap, her stream'den bir tamponlanmış eleman; external merge sort'un birleştirme aşaması. Kafka'da partition'lar arası global sıra için benzer fikir.)
2. Eşit değerlerde girdi sırası korunmalı (kararlı birleştirme). (Beklenen: heap elemanına liste index'i ekle, comparator'da ikinci kriter yap.)
3. Divide and conquer'ı iteratif yaz; özyineleme derinliği neden burada sorun değil? (Beklenen: aralık iki katına çıkarak birleştirme; derinlik log k olduğu için özyinelemeli versiyon da güvenli.)

Benzer problemler

• Merge Two Sorted Lists (LeetCode 21): temel birleştirme adımı.
• Kth Smallest Element in a Sorted Matrix (LeetCode 378): k sıralı satır + heap.
• Find K Pairs with Smallest Sums (LeetCode 373).
• Smallest Range Covering Elements from K Lists (LeetCode 632).
• Top K Frequent Elements (LeetCode 347): heap ile seçim (bu sette: top-k-frequent-elements).