Bağlı Liste Palindrom mu? En İyi Çözüm Adım Adım

Bağlı listelerde palindrom kontrolü, veri yapıları ve algoritmaların temel taşlarından biri olarak kabul edilir. Peki, verileri baştan sona taradığınızda ortaya çıkan dizinin aynı şekilde tersten de okunabilmesi ne anlama gelir? En basit haliyle, bir palindrom, ilk ve son karakterden orta noktaya doğru ilerlerken simetrik olarak eşleşen bir yapıdır. Bu kavramı bağlı listelere uyguladığınızda, problemi çözmek için dikkatli bir yaklaşım gerekir — zira bağlı listelerde rastgele erişim mümkün değildir.

Neden Bağlı Liste Palindrom Kontrolü Zordur?

Bağlı listelerin en belirgin özelliği, her düğümün yalnızca bir sonraki düğüme bağlantı içermesidir. Bu durum, listenin sonundan başına doğru hareket etmek için ekstra veri yapılarına ihtiyaç duyulmasına neden olur. Örneğin, bir dizi palindromik mi diye kontrol ederken, iki uçtan başlayıp ortada buluşabilirsiniz. Ancak bağlı listelerde aynı işlemi doğrudan gerçekleştirmek mümkün değildir.

Veri yapısının bu kısıtı, problemi çözmek için farklı stratejiler geliştirmeyi gerektirir. En yaygın yaklaşımlardan biri, tüm düğüm değerlerini bir diziye aktarmak ve ardından standart palindrom algoritmasını uygulamaktır. Bu yöntem basit olsa da, ekstra bellek kullanımına yol açar. Peki, bellek kullanımını en aza indirirken aynı sonuca ulaşabilir miyiz?

Verimsiz Yöntem: Tüm Düğümleri Dizi Olarak Saklamak

Bu yaklaşımda, bağlı listenin tüm düğüm değerleri bir diziye aktarılır. Ardından, dizi üzerinde iki işaretçi kullanılarak ilk ve son elemanlar karşılaştırılır.

Java Örneği

public boolean isPalindrome(ListNode head) {
    List<Integer> values = new ArrayList<>();
    while (head != null) {
        values.add(head.val);
        head = head.next;
    }
    int left = 0;
    int right = values.size() - 1;
    while (left < right) {
        if (!values.get(left).equals(values.get(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Karmaşıklık Analizi

• Zaman Karmaşıklığı: O(N) — listenin tamamı bir kez taranır.
• Alan Karmaşıklığı: O(N) — tüm düğüm değerleri bir dizi olarak saklanır.

Bu yöntem, basitliği nedeniyle tercih edilebilir, ancak büyük bağlı listelerde bellek tüketimi önemli bir dezavantaj oluşturur.

Optimize Edilmiş Yöntem: Ortayı Bul, İkinci Yarıyı Ters Çevir

Bağlı liste palindrom kontrolünde bellek kullanımını minimize etmek için kullanılan en etkili yöntemlerden biri, listenin ortasını bulmak ve ikinci yarıyı ters çevirmektir. Bu sayede, ilk yarı ile ikinci yarı karşılaştırılabilir hale gelir.

Adım Adım İşlem

1. Ortayı Bul: İki işaretçi kullanarak (yavaş ve hızlı) listenin ortasını belirleyin. Hızlı işaretçi, yavaş işaretçiden iki kat hızlı ilerleyerek listenin sonuna ulaştığında, yavaş işaretçi tam ortada durur.

1. İkinci Yarıyı Ters Çevir: Ortadan sonraki düğümlerin bağlantı yönlerini tersine çevirin. Bu işlem, ikinci yarıyı baştan sona okuyabilir hale getirir.

1. İki Yarıyı Karşılaştır: İlk yarıdaki düğümlerin değerlerini, ters çevrilmiş ikinci yarıdaki düğümlerin değerleriyle karşılaştırın. Eğer tüm değerler eşleşiyorsa, liste palindromiktir.

Optimize Java Çözümü

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // Ortayı bul
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // İkinci yarıyı ters çevir
        ListNode secondHalf = reverseList(slow.next);

        // Her iki yarıyı karşılaştır
        ListNode first = head;
        ListNode second = secondHalf;
        while (second != null) {
            if (first.val != second.val) {
                return false;
            }
            first = first.next;
            second = second.next;
        }
        return true;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Karmaşıklık Analizi

• Zaman Karmaşıklığı: O(N) — listenin tamamı üç kez taranır (orta bulma, ters çevirme, karşılaştırma).
• Alan Karmaşıklığı: O(1) — yalnızca birkaç geçici düğüm kullanılır.

Gerçek Dünya Örnekleriyle Anlama

Bir bağlı listeyi palindromik olarak değerlendirebilmek için yukarıdaki yöntemin nasıl çalıştığını adım adım inceleyelim. Örneğin, 1 -> 2 -> 2 -> 1 listesini ele alalım.

1. Ortayı Bul:

• Yavaş işaretçi ikinci düğüme (2), hızlı işaretçi son düğüme (1) ulaşır.
• Liste: 1 -> 2 -> 2 -> 1

1. İkinci Yarıyı Ters Çevir:

• İkinci yarı 2 -> 1, ters çevrildikten sonra 1 -> 2 olur.

1. Karşılaştır:

• İlk yarı: 1 -> 2
• Ters çevrilmiş ikinci yarı: 1 -> 2
• Tüm değerler eşleştiğinden sonuç true olur.

Mülakatlarda Başarılı Olmak İçin İpuçları

Bağlı liste palindrom problemi, birçok mülakat sorusunda karşınıza çıkabilecek temel bir algoritmik yaklaşımdır. Bu problemi çözerken aşağıdaki adımları izleyerek hem doğru hem de optimize edilmiş bir çözüm sunabilirsiniz:

• İki İşaretçi Tekniği: Yavaş ve hızlı işaretçiler kullanarak listenin ortasını verimli bir şekilde bulun.
• İn-Place İşlemler: Bağlantıları değiştirirken ek bellek kullanmamaya özen gösterin.
• Kenar Durumları: Boş liste, tek düğümden oluşan liste gibi özel durumları kontrol edin.
• Zaman ve Alan Karmaşıklığı: Her adımda karmaşıklıkları hesaplayarak optimize edilmiş bir çözüm sunduğunuzdan emin olun.

Sık Karşılaşılan Benzer Problemler

Bu teknik, yalnızca palindromik bağlı listelerin kontrolünde değil, birçok algoritmik problemde de uygulanabilir:

• Bağlı Listeyi Yeniden Düzenleme: Listenin ilk ve son düğümlerini eşleştirerek ortada buluşmalarını sağlama.
• Çiftlerin Maksimum Toplamı: Bağlı listenin karşılıklı düğümlerinin toplamını hesaplama.
• Bağlı Listeyi İkiye Bölme: Listenin ilk ve ikinci yarılarını ayrı ayrı işleme.

Bu yaklaşımları öğrenerek, bağlı liste problemlerinde daha hızlı ve verimli çözümler geliştirebilirsiniz.

Sonuç: Bellek Verimliliği ve Performans Dengesi

Bağlı liste palindrom kontrolü, algoritmik düşünme ve bellek yönetimi becerilerini bir araya getiren önemli bir problemdir. Verimsiz yöntemlerle karşılaştırıldığında, optimize edilmiş çözümler yalnızca bellek kullanımını azaltmakla kalmaz, aynı zamanda problemi daha hızlı bir şekilde çözme olanağı sunar.

Gelecekteki projelerinizde veya teknik mülakatlarınızda karşılaşabileceğiniz bağlı liste problemlerinde, bu yöntemi kullanarak hem performansı hem de verimliliği en üst düzeye çıkarabilirsiniz. Unutmayın, doğru algoritmayı seçmek, problemi çözmek kadar önemlidir.