Bağlı listeyi ters çevir

Problem

Tek yönlü bir bağlı listenin baş düğümü veriliyor. Listeyi ters çevir ve yeni baş düğümü döndür. Yeni düğüm oluşturmak yerine mevcut düğümlerin next bağlantılarını değiştirmen bekleniyor.

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

Girdi:  null
Çıktı:  null

Netleştirme soruları

• Liste boş (null) olabilir mi?
• Yerinde mi değiştirmeliyim, yoksa yeni bir liste mi üretmeliyim? (Girdinin başka yerlerde kullanılıp kullanılmadığı önemli.)
• İteratif mi özyinelemeli mi isteniyor, ikisi de mi?
• Liste ne kadar uzun olabilir? (Özyineleme derinliği için kritik.)

İpuçları

Yaklaşım

Brute force: Değerleri bir ArrayList'e ya da stack'e kopyala, sonra listeyi baştan gezip değerleri ters sırayla yaz (ya da yeni düğümler oluştur). O(n) zaman ama O(n) ek bellek; ayrıca değer kopyalamak, düğümlerin kimliğine bağlı başka referanslar varsa davranışı değiştirir.

İteratif, üç işaretçi: previous = null, current = head ile başla. Her adımda:

1. next = current.next (kalan listeyi kaybetme),
2. current.next = previous (oku çevir),
3. previous = current, current = next (ilerle).

current null olduğunda previous yeni baştır. Değişmez: her adımın sonunda previous, şimdiye kadar işlenmiş kısmın ters çevrilmiş halinin başıdır; current ise henüz dokunulmamış kısmın başıdır. O(n) zaman, O(1) ek bellek.

Özyinelemeli: reverse(head.next) kalan listeyi ters çevirir ve yeni başı döndürür. Bu noktada head.next hâlâ eski ikinci düğümü, yani ters çevrilmiş listenin son düğümünü gösterir; head.next.next = head ile head'i sona ekleriz. head.next = null satırı unutulursa ilk iki düğüm arasında döngü oluşur. O(n) zaman, O(n) çağrı yığını.

Java'da özyinelemeli versiyonun ciddi bir pratik sınırı var: JVM tail call optimization yapmaz ve varsayılan thread stack'i (genelde 512 KB-1 MB) birkaç on bin ile birkaç yüz bin çerçeve arasında dolar. Testte 1.000.000 düğümlü listede özyinelemeli versiyon StackOverflowError attı, iteratif versiyon sorunsuz çalıştı. Production kodunda iteratif versiyon tercih edilir.

Java çözümü

public final class ReverseLinkedList {

    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: O(n) zaman, O(1) ek bellek
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;                          // 1) kalan listeyi kaybetme
            current.next = previous;                               // 2) oku ters çevir
            previous = current;                                    // 3) iki işaretçiyi bir adım ilerlet
            current = next;
        }
        return previous;                                           // yeni baş: eski son düğüm
    }

    // Özyinelemeli: O(n) zaman, O(n) çağrı yığını
    public ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseListRecursive(head.next);
        head.next.next = head;                                     // arkamdaki düğüm artık beni göstersin
        head.next = null;                                          // eski bağı kopar, yoksa döngü oluşur
        return newHead;
    }
}

ListNode, LeetCode'daki tanıma uygun olarak sınıfın içinde iç içe tanımlandı; testler aynı paketten erişiyor.

Karmaşıklık

• İteratif: O(n) zaman, O(1) ek bellek.
• Özyinelemeli: O(n) zaman, O(n) bellek (çağrı yığını).
• Kopyalama yaklaşımı: O(n) zaman, O(n) bellek.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı. Her test, listenin sonunda null'a ulaşıldığını (yanlışlıkla döngü oluşmadığını) bir adım sınırıyla da kontrol ediyor.

Mülakatçı için

Çok kısa bir soru; genelde daha büyük bir linked list sorusunun (Reverse Nodes in k-Group, Palindrome Linked List, Reorder List) parçası ya da ısınmadır. Gözlenecek şey işaretçi işlemlerinin doğru sırası ve adayın kodu bir çizimle ya da küçük bir örnekle doğrulama alışkanlığı. Özyinelemeli versiyonu yazan adaya stack derinliği sorusunu sormak, JVM bilgisini ölçmenin iyi bir yoludur.

İpucu zamanlaması: Aday kopyalama yaklaşımıyla başlarsa kabul et ve "O(1) ek bellekle?" diye sor. İşaretçi sırasında kaybolursa kâğıda üç kutu çizip okları adım adım çevirmesini öner. Özyinelemeli versiyonda head.next = null eksikse iki düğümlü listeyle yürütmesini iste.

Takip soruları:

1. Sadece left. ve right. düğümler arasını ters çevir. (Beklenen: left'ten önceki düğümü bul, aradaki kısmı aynı üç işaretçiyle çevir, uçları yeniden bağla; dummy düğüm sınır durumlarını kolaylaştırır. LeetCode 92.)
2. Listeyi k'lık gruplar halinde ters çevir. (Beklenen: LeetCode 25; grup başı/sonu takibi, eksik son grubun çevrilmemesi.)
3. Bir listenin palindrom olup olmadığını O(1) ek bellekle kontrol et. (Beklenen: hızlı/yavaş işaretçiyle ortayı bul, ikinci yarıyı ters çevir, karşılaştır, istenirse geri çevir.)

Benzer problemler

• Reverse Linked List II (LeetCode 92).
• Reverse Nodes in k-Group (LeetCode 25).
• Palindrome Linked List (LeetCode 234).
• Reorder List (LeetCode 143).
• Linked List Cycle (LeetCode 141) (bu sette: linked-list-cycle).