Bağlı liste uygulamaları ve tekrar

Bu hafta yeni yapı yok. İlk üç haftada kurduğun düğüm becerisini, sınavda en sık istenen dört algoritmada kullanıyorsun: listeyi ters çevirmek, ortayı bulmak, döngüyü tespit etmek ve iki sıralı listeyi birleştirmek. Dördü de O(n) sürede ve ekstra dizi kullanmadan çalışır. Sonda liste ile diziyi karşılaştıran bir özet var; vize öncesi tekrar için bu sayfa yeter.

Altın kurallar:

1. Bir referansı değiştirmeden önce, ihtiyacın olan devamı sakla.
2. İki referans tekniği (two pointers): biri hızlı biri yavaş, ya da biri önde biri arkada.
3. Sahte baş düğüm (dummy node) “liste boş mu, head değişiyor mu” kontrollerini yok eder.
4. Her metodu boş liste ve tek elemanlı listede kafanda dene.

Tekrar: üç haftanın özeti

* Dizide yer varsa. Dolarsa yeni diziye kopyalama O(n).

Listeyi ters çevirme (reverse)

Fikir: her düğümün okunu geriye çevir. Ama curr.next’i değiştirdiğin an listenin geri kalanına ulaşamazsın, o yüzden önce sakla.

static Node reverse(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node next = curr.next;   // 1) devamı sakla
        curr.next = prev;        // 2) oku ters çevir
        prev = curr;             // 3) prev bir ileri
        curr = next;             // 4) curr bir ileri
    }
    return prev;
}

1 2 3 4 üzerinde her turdan sonraki durum (program çıktısı):

step 1: prev-list = 1 | curr = 2
step 2: prev-list = 2 1 | curr = 3
step 3: prev-list = 3 2 1 | curr = 4
step 4: prev-list = 4 3 2 1 | curr = null
4 3 2 1

TUZAK · return head yazmak. Döngü bitince eski head (1) artık listenin son düğümüdür ve next’i null. Yeni baş prev’dir. Çağıran tarafta da head = reverse(head); diye atamayı unutma.

Ortadaki düğüm: yavaş ve hızlı referans

Önce uzunluğu sayıp sonra n/2 adım yürümek de doğru cevaptır (iki geçiş). Tek geçişte yapmak için iki referans kullan: fast iki adım atarken slow bir adım atar. fast sona vardığında slow yolun yarısındadır.

static Node middle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

1..7 -> 4
1..6 -> 4
10 20 30 40 50 -> 30

Çift uzunlukta iki orta vardır (1..6 için 3 ve 4). Bu döngü koşuluyla ikinci orta döner. Soru ilk ortayı isterse koşulu fast.next != null && fast.next.next != null yap.

Döngü tespiti (Floyd)

Hatalı bir kod son düğümün next’ini yanlışlıkla önceki bir düğüme bağlamış olabilir. Bu listeyi yazdırmaya çalışırsan sonsuz döngüye girersin. Döngü olup olmadığını O(1) bellekle anlamak için aynı slow/fast fikri kullanılır: pistte koşan iki kişiden hızlı olan, pist dairesel ise yavaşı mutlaka bir tur bindirir.

static boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

İz: 1 → 2 → 3 → 4 → 5 ve 5 tekrar 3’ü gösteriyor.

adım   slow   fast
 0      1      1
 1      2      3
 2      3      5
 3      4      4    (5 → 3 → 4)  buluştular → true

Program da aynı sonucu verdi: met after 3 steps, buluşma düğümü 4. 6 düğümlü ve sonu başa bağlanan listede 6 adımda 1’de buluşurlar.

İPUCU · Neden mutlaka yakalar? İkisi de döngüye girdikten sonra her adımda hızlı olan bir düğüm fazla ilerler, yani aralarındaki mesafe 1 azalır. Mesafe 0’a düşünce buluşurlar, atlayıp geçemezler.

İki sıralı listeyi birleştirme (merge)

Merge sort’un kalbi bu işlem (14. hafta). İki listenin başlarını karşılaştır, küçüğü sonuca ekle, o listede bir ilerle.

static Node merge(Node a, Node b) {
    Node dummy = new Node(0), t = dummy;
    while (a != null && b != null) {
        if (a.data <= b.data) { t.next = a; a = a.next; }
        else                  { t.next = b; b = b.next; }
        t = t.next;
    }
    t.next = (a != null) ? a : b;
    return dummy.next;
}

1 2 3 4 7 8 9
2 5 10 10 12 15
3 6

Üçüncü satır merge(null, 3 6): biri boşsa diğeri aynen döner. dummy olmasaydı ilk elemanı ayrıca seçip head yapmak gerekirdi; dummy bu özel durumu ortadan kaldırır. Sonuç dummy.next’tir, dummy’nin kendisi değil.

<= kullanmak eşit değerlerde önce a’dan alır. Bu, sıralama algoritmalarında kararlılık (stability) dediğimiz özelliği korur.

Diğer iki referans kalıpları

Sondan k. eleman. lead’i k adım öne al, sonra ikisini birlikte yürüt. lead null olduğunda trail sondan k. düğümdedir. 10 20 30 40 50 60 ve k = 2 için 50.

Sıralı listede tekrarları silme. Eşit komşuyu atla, ilerleme; farklıysa ilerle. 1 1 2 3 3 3 4 → 1 2 3 4.

İkişer yer değiştirme. p = p.next.next ile ikişer atlayıp veri takası. 1 2 3 4 5 → 2 1 4 3 5.

Liste mi, dizi mi?

Kural: çok rastgele erişim varsa dizi, çok baştan/ortadan ekleme silme varsa liste.

Sık yapılan hatalar

static Node reverse(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node next = curr.next;   // devamı sakla
        curr.next = prev;        // oku ters çevir
        prev = curr;             // bir ileri
        curr = next;
    }
    return prev;                 // yeni head
}

Node slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
return slow;

static boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;   // aynı DÜĞÜM (==), aynı veri değil
    }
    return false;
}

static Node merge(Node a, Node b) {
    Node dummy = new Node(0), t = dummy;
    while (a != null && b != null) {
        if (a.data <= b.data) { t.next = a; a = a.next; }
        else                  { t.next = b; b = b.next; }
        t = t.next;
    }
    t.next = (a != null) ? a : b;   // kalan liste
    return dummy.next;
}

Node p = head;
while (p != null && p.next != null) {
    if (p.data == p.next.data) p.next = p.next.next;
    else p = p.next;
}
print(head);

Node lead = head, trail = head;
for (int i = 0; i < k; i++) lead = lead.next;
while (lead != null) { lead = lead.next; trail = trail.next; }
return trail.data;

for (Node p = head; p != null && p.next != null; p = p.next.next) {
    int t = p.data;
    p.data = p.next.data;
    p.next.data = t;
}
print(head);

Node x = build(3, 6, 9);
x = reverse(x);
Node y = build(1, 5);
Node z = merge(y, reverse(x));
System.out.println(str(z) + " middle=" + middle(z).data);