LeetCode 148: Bağlantılı Listeyi Sıralama

LeetCode 148: Bağlantılı Listeyi Sıralama

Merhaba, ben Fatih Soysal. Bu makalede, LeetCode’un 148. problemi olan “Bağlantılı Listeyi Sıralama” problemini detaylı bir şekilde ele alacağız. Problem, verilen bir bağlantılı listeyi artan sırada sıralamamızı istiyor. Bu problemi çözmek için birkaç farklı yaklaşım mevcuttur; ancak en verimli yöntemlerden biri Merge Sort algoritmasıdır. Öncelikle problemi daha iyi anlamak için, problemin detaylarına ve Merge Sort algoritmasının nasıl çalıştığına bakalım.

Problem Tanımı

Verilen bir bağlantılı listeyi, elemanlarını artan sırada sıralayarak yeni bir bağlantılı liste oluşturmamız gerekiyor. Bu işlem sırasında orijinal bağlantılı listeyi değiştirmemeliyiz. Örneğin, 4->2->1->3 gibi bir listeyi 1->2->3->4 şeklinde sıralamamız gerekiyor.

Merge Sort ile Çözüm

Merge Sort, böl ve yönet (divide and conquer) yaklaşımı kullanan bir sıralama algoritmasıdır. Bu algoritma, listeyi sürekli olarak ikiye bölerek, her bir alt listenin sıralı olmasını sağlar. Daha sonra, bu sıralı alt listeleri birleştirerek, tüm listenin sıralı halini elde ederiz. Bu yöntem, bağlantılı listeler için oldukça uygundur, çünkü bağlantılı listelerde elemanların rastgele erişimi yavaştır.

Algoritmanın adımları şunlardır:

1. Listeyi ortadan ikiye bölün.
2. Her bir alt listeyi rekursif olarak Merge Sort ile sıralayın.
3. Sıralı iki alt listeyi birleştirin.

Kod Örneği (Java)

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode mid = getMid(head);
    ListNode right = sortList(mid);
    mid.next = null;
    ListNode left = sortList(head);
    return merge(left, right);
}

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

private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Bu kod, Merge Sort algoritmasını kullanarak bağlantılı listeyi sıralar. getMid fonksiyonu listenin ortasını bulur, merge fonksiyonu ise iki sıralı listeyi birleştirir. Sonuç olarak, sıralama işlemi logn zaman karmaşıklığı ile gerçekleştirilir.

Alternatif Çözümler

Bu problem, diğer sıralama algoritmaları ile de çözülebilir. Ancak, Merge Sort, bağlantılı listeler için en uygun algoritmalardan biridir. Diğer algoritmalar, bağlantılı listelerin yapısı nedeniyle daha düşük performans gösterebilir.

Başka bir çözüm olarak, bağlantılı listeyi önce bir diziye aktarabilir, diziyi sıralamak için hızlı bir algoritma kullanabilir ve ardından sıralama sonucundan yeni bir bağlantılı liste oluşturabilirsiniz. Ancak bu yaklaşım, ek bellek gerektirir.

Sonuç

LeetCode 148 problemi, bağlantılı liste sıralama konusunda önemli bir problemdir. Merge Sort algoritması, bu problem için verimli ve etkili bir çözüm sunmaktadır. Umarım bu makale, problemi anlamanıza ve çözmenize yardımcı olmuştur. Daha fazla bilgi için fatihsoysal.com sitesini ziyaret edebilirsiniz. Ayrıca, konu hakkında daha fazla bilgi edinmek için bu linki inceleyebilirsiniz.

#Etiketler

#LeetCode #148 #BağlantılıListe #Sıralama #MergeSort #Algoritma #Programlama #Java #VeriYapıları #FatihSoysal