Bağlı listede ikili yer değiştirme

Problem

Tek yönlü bir bağlı listenin baş düğümü veriliyor. Listeyi baştan itibaren ikişerli gruplara ayır ve her gruptaki iki düğümün yerini değiştir; yeni baş düğümü döndür. Düğüm sayısı tekse son düğüm yerinde kalır. Düğümlerin içindeki değerleri değiştirmek yasak: yer değiştirme next bağlantılarıyla yapılmalı.

Girdi:  1 -> 2 -> 3 -> 4 -> 5
Çıktı:  2 -> 1 -> 4 -> 3 -> 5

Girdi:  7
Çıktı:  7

Goldman Sachs'ın DSA turunda bir aday bu soruyu "linked list'i ikili gruplar halinde ters çevir" diye raporladı; ilk örnek raporun kendisinden. Bu, Reverse Nodes in k-Group (LeetCode 25) probleminin k = 2 hâlidir ve görüşmede genelleştirme takip sorusu olarak gelir.

Netleştirme soruları

• Liste boş ya da tek düğümlü olabilir mi?
• Değerleri değiştirmek kabul mü, yoksa düğümlerin kendisi mi yer değiştirmeli? (Düğümlere dışarıdan referans tutuluyorsa fark önemlidir.)
• Tek sayıda düğüm varsa son düğüm olduğu gibi mi kalır?
• Liste ne kadar uzun olabilir? (Özyinelemeli çözümün stack derinliği.)

İpuçları

Yaklaşım

Brute force, değerleri değiştir: Listeyi ikişer ikişer gez ve val alanlarını takas et. O(n) zaman, O(1) bellek ve çok kısa. Ama problem değer değiştirmeyi yasaklıyor; gerçek hayatta da düğüm büyük bir nesne olabilir ya da başka yerlerden düğümlere referans tutuluyor olabilir. Mülakatta "bunu yapabilirdim ama düğümleri taşımam isteniyor" diye söylemek yeterli.

Brute force, diziye kopyala: Düğüm referanslarını bir ArrayList'e al, dizide komşuları takas et, sonra next'leri baştan bağla. O(n) zaman ama O(n) ek bellek. Doğruluğunu kanıtlamak kolay olduğu için testlerde referans çözüm olarak bu kullanıldı.

İteratif, dummy düğüm: dummy.next = head ile başla, beforePair = dummy. beforePair'den sonra en az iki düğüm olduğu sürece:

1. first = beforePair.next, second = first.next,
2. first.next = second.next (first, çiftten sonrasını göstersin; kalan liste kaybolmaz),
3. second.next = first,
4. beforePair.next = second (önceki kısım yeni başa bağlansın),
5. beforePair = first (first artık çiftin sonu ve bir sonraki çiftin öncülü).

Döngü bitince dummy.next yeni baştır. Değişmez: her adımın sonunda dummy'den beforePair'e kadar olan kısım işlenmiş ve doğru bağlıdır; beforePair.next'ten itibaren olan kısım hiç dokunulmamış orijinal listedir. O(n) zaman, O(1) ek bellek. Dummy düğüm, baş düğümün değiştiği özel durumu ortadan kaldırır.

Özyinelemeli: İlk iki düğümü takas et, üçüncü düğümden itibaren kalan listeyi özyinelemeyle çöz ve sonucu eski başa bağla: head.next = swap(second.next), second.next = head, return second. Kısa ve okunaklı ama n/2 derinliğinde çağrı yığını kullanır. JVM tail call optimization yapmadığı için testte 1.000.000 düğümlü listede StackOverflowError attı; iteratif versiyon sorunsuz çalıştı.

Genelleştirme, k'lı gruplar (LeetCode 25): Aynı iskelet: beforeGroup'tan k adım ilerleyip grubun son düğümünü bul; k düğüm yoksa dur (eksik son grup olduğu gibi kalır). Grubu, previous başlangıçta afterGroup olacak şekilde klasik üç işaretçiyle ters çevir; böylece ters çevrilen grubun sonu doğrudan geri kalan listeye bağlanır. Sonra beforeGroup.next = groupEnd ve beforeGroup = groupStart. k = 2 için sonuç swapPairs ile aynıdır.

Java çözümü

public final class SwapNodesInPairs {

    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; }
    }

    // İteratif, dummy düğüm: O(n) zaman, O(1) ek bellek
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode beforePair = dummy;                               // çiftten önceki düğüm
        while (beforePair.next != null && beforePair.next.next != null) {
            ListNode first = beforePair.next;
            ListNode second = first.next;

            first.next = second.next;                              // 1) first, çiftten sonrasını göstersin
            second.next = first;                                   // 2) second, first'ü göstersin
            beforePair.next = second;                              // 3) önceki kısım second'a bağlansın

            beforePair = first;                                    // first artık çiftin sonu
        }
        return dummy.next;
    }

    // Özyinelemeli: O(n) zaman, O(n) çağrı yığını (n/2 çerçeve)
    public ListNode swapPairsRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode second = head.next;
        head.next = swapPairsRecursive(second.next);               // kalan listeyi çöz, sonuca bağlan
        second.next = head;
        return second;
    }

    // Takip (LeetCode 25): k'lık grupları ters çevir, eksik son grup olduğu gibi kalır. O(n), O(1).
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 1) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode beforeGroup = dummy;
        while (true) {
            ListNode groupEnd = beforeGroup;
            for (int i = 0; i < k && groupEnd != null; i++) {
                groupEnd = groupEnd.next;
            }
            if (groupEnd == null) {
                return dummy.next;                                 // k düğüm kalmadı
            }
            ListNode afterGroup = groupEnd.next;
            ListNode groupStart = beforeGroup.next;

            ListNode previous = afterGroup;                        // grubu ters çevir, sonunu afterGroup'a bağla
            ListNode current = groupStart;
            while (current != afterGroup) {
                ListNode next = current.next;
                current.next = previous;
                previous = current;
                current = next;
            }
            beforeGroup.next = groupEnd;                           // eski son, grubun yeni başı
            beforeGroup = groupStart;                              // eski baş, grubun yeni sonu
        }
    }
}

ListNode, LeetCode'daki tanıma uygun olarak sınıfın içinde iç içe tanımlandı; testler aynı paketten erişiyor. reverseKGroup takip sorusu için eklendi; k <= 1 için liste değişmeden döner.

Karmaşıklık

k'lı gruplarda her düğüm bir kez sayılır (grup sonunu bulmak için) ve bir kez ters çevrilir; toplam O(n).

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı. 0'dan 40'a kadar her liste uzunluğu için iteratif ve özyinelemeli versiyon, düğüm referanslarını diziye kopyalayıp takas eden brute force ile karşılaştırıldı. Karşılaştırma değerlerle değil düğüm kimliğiyle (==) yapıldı; böylece yeni düğüm yaratan ya da değer takas eden bir çözüm testi geçemez. Her dolaşma bir adım sınırıyla yapıldı (döngü oluşursa yakalanır). reverseKGroup, her uzunluk için k = 0 ile n + 2 arasındaki tüm değerlerle aynı brute force'a karşı doğrulandı.

Mülakatçı için

Kısa ama işaretçi disiplinini çok net gösteren bir soru. Gözlenecek şeyler: adayın kâğıda kutu ve ok çizip önce atamaların sırasını belirlemesi, baş düğüm için özel durum yazmak yerine dummy düğüm kullanması ve kodu iki ile üç düğümlü listelerle yürütmesi. Değer takası öneren adaya "düğümleri taşıman isteniyor" demek yeterli; bunu kendi söyleyen aday ayrıca puan alır.

İpucu zamanlaması: Aday baş düğümü ayrı ele alıp koşul yığmaya başlarsa ikinci ipucuyla dummy'yi öner. Atamaları yanlış sırada yapıp listeyi kaybederse üç düğümlü bir örnekte okları adım adım çizdir. Zaman kalırsa k'lı grupları sor; iskeleti koruyup sadece "grup sonunu bul + grubu ters çevir" kısmını değiştirmesini bekle.

Takip soruları:

1. Listeyi k'lık gruplar halinde ters çevir; eksik son grup olduğu gibi kalsın (LeetCode 25). (Beklenen: grup sonunu bulmak için k adım ileri bak, grubu previous = afterGroup ile ters çevir, öncülü bağla; O(n), O(1).)
2. Eksik son grup da ters çevrilsin. (Beklenen: grup sonu bulunamazsa durmak yerine kalan kısmı ters çevir; tek satırlık değişiklik ama sözleşme farkını sormak gerekir.)
3. Liste çift yönlü (prev ve next) olsaydı ne değişirdi? (Beklenen: her takasta üç yerine altı bağlantı, üç next ve üç prev; prev güncellemelerini unutmamak, en sık hata kaynağı.)

Benzer problemler

• Reverse Linked List (LeetCode 206) (bu sette: reverse-linked-list).
• Reverse Nodes in k-Group (LeetCode 25): bu problemin genel hâli.
• Reverse Linked List II (LeetCode 92): aralığı ters çevirme, dummy düğüm.
• Odd Even Linked List (LeetCode 328): bağlantıları yeniden düzenleme.
• Merge k Sorted Lists (LeetCode 23) (bu sette: merge-k-sorted-lists).