Bu yazımda LeetCode sitesindeki 21. Merge Two Sorted Lists (İki Sıralı Bağlantılı Listeyi Birleştirme) sorusunu anlatıp, çözümünü paylaşacağım. İlk önce sorunun tanımına geçelim:

list1 ve list2 adında sıralı liste (linked list) verilsin. Bu verilen 2 sıralı listeyi tek bir liste olacak şekilde birleştirip, birleşen yeni listenin başını (head) döndürün.

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

Görseldeki örnek üzerinden anlatmak gerekirse:
list1: 1 -> 1 -> 2 -> 5 -> 8
list2: 3 -> 4 -> 6
list3: (döndüreceğimiz yeni liste)
şeklide olsun. Burada hemen ilk yapmamız gereken şey listenin ilk elemanlarını karşılaştırmak ve küçük olanı yeni listenin ilk elemanı yapmak. Sırası ile gidelim:

İlk önce ilk elemanları karşılaştıralım. 1 < 3 olduğu için 1’i döndüreceğimiz listeye ekleyip list1 içinde 1 adım ilerleyelim. Yeni durumumuz:

list1: 1 -> 2 -> 5 -> 8
list2: 3 -> 4 -> 6
list3: 1

Şimdi tekrardan ilk elemanları karşılaştıralım. 1 < 3 olduğu için 1’i döndüreceğimiz listeye ekleyip list1 içinde 1 adım ilerleyelim. Yeni durumumuz:

list1: 2 -> 5 -> 8
list2: 3 -> 4 -> 6
list3: 1 -> 1

Şimdi tekrardan ilk elemanları karşılaştıralım. 2 < 3 olduğu için 2’i döndüreceğimiz listeye ekleyip list1 içinde 1 adım ilerleyelim. Yeni durumumuz:

list1: 5 -> 8
list2: 3 -> 4 -> 6
list3: 1 -> 1 -> 2

Şimdi tekrardan ilk elemanları karşılaştıralım. 3 < 5 olduğu için 3’ü döndüreceğimiz listeye ekleyip list2 içinde 1 adım ilerleyelim. Yeni durumumuz:

list1: 5 -> 8
list2: 4 -> 6
list3: 1 -> 1 -> 2 – > 3

Şimdi tekrardan ilk elemanları karşılaştıralım. 4 < 5 olduğu için 4’ü döndüreceğimiz listeye ekleyip list2 içinde 1 adım ilerleyelim. Yeni durumumuz:

list1: 5 -> 8
list2: 6
list3: 1 -> 1 -> 2 – > 3 -> 4

Şimdi tekrardan ilk elemanları karşılaştıralım. 5 < 6 olduğu için 5’i döndüreceğimiz listeye ekleyip list1 içinde 1 adım ilerleyelim. Yeni durumumuz:

list1: 8
list2: 6
list3: 1 -> 1 -> 2 – > 3 -> 4 -> 5

Şimdi tekrardan ilk elemanları karşılaştıralım. 6 < 8 olduğu için 5’i döndüreceğimiz listeye ekleyip list2 içinde 1 adım ilerleyelim. Yeni durumumuz:

list1: 8
list2:
list3: 1 -> 1 -> 2 – > 3 -> 4 -> 5 -> 6

List1 de 8 varken list2 boş olduğu için 8’i döndüreceğimiz listeye ekleyip list1 içinde 1 adım ilerleyelim. Yeni durumumuz:

list1:
list2:
list3: 1 -> 1 -> 2 – > 3 -> 4 -> 5 -> 6 -> 8

list1 ve list2 boş olduğu için list3’ü döndürüp görevi bitirebiliriz.

Şimdi bu nasıl koda dökeceğimize bakalım:

İlk önce list3 için tanımlarımızı yapalım ve baş (head) değerini kaybetmemek için başka bir değişkende daha saklayalım:

ListNode list3 = new ListNode();
ListNode tmp = list3;

Eğer list1 ve list2 içinde hala elemanlar kaldıysa dönecek bir while döngüsü kuralım.

while(list1 != null || list2 != null)

Daha sonra karşılaştırma yapabilmek için değer geçici değişkenlerde tutalım. Burada dikkat etmemiz gereken şey listelerden birisinin boş olabilme ihtimalidir. Eğer o anda düğüm (node) boş ise boş olmayanın değerini alabilmek için o düğümün değerini olabilen en yüksek değere atama yapıyoruz.

int iList1Deger = list1 == null ? int.MaxValue : list1.val;
int iList2Deger = list2 == null ? int.MaxValue : list2.val;

Küçük olan değeri bulup ona ait listeyi bir adım öteleme işlemini yapalım.

int val = 0;
if (iList1Deger < iList2Deger)
{
    val = iList1Deger;
    list1 = list1.next;
}
else
{
    val = iList2Deger;
    list2 = list2.next;
}

Elde ettiğimiz değeri döndüreceğimiz list3 listesinin yedeğinin sonraki elemanına ekleyelim.

ListNode l1 = new ListNode(val);
tmp.next = l1;
tmp = l1;

Bütün işlemler bittikten list3‘ün sonraki elemanını geri döndürelim. Çünkü list3‘ün ilk elemanın bizim için bir önemi yok ilk ekleyeceğimiz elemanın hangi listeden geleceğini bilmediğimiz için böyle bir tanımlama yaptık. Kodun son hali aşağıdaki gibi olacaktır:

 public ListNode MergeTwoLists(ListNode list1, ListNode list2) 
    {
        ListNode list3 = new ListNode();
        ListNode tmp = list3;
        while((list1 != null || list2 != null ))
        {
            int iList1Deger = list1 == null ? int.MaxValue : list1.val; 
            int iList2Deger = list2 == null ? int.MaxValue : list2.val;
            int val = 0;
            if(iList1Deger < iList2Deger)
            {
                val = iList1Deger;
                list1 = list1.next;
            }
            else
            {
                val = iList2Deger;
                list2 = list2.next;
            }
            ListNode l1 = new ListNode(val);
            tmp.next = l1;
            tmp = l1;
        }

        
        return list3.next;

    }

Bu problem istenirse özyineleme (recursive) kullanılarak da çözülebilir. Bu da şöyle olacaktır:

Eğer list1 boş ise list2‘yi döndür.
Eğer list2 boş ise list1‘i döndür.
Eğer list1‘deki değer list2‘deki değerden küçük ise list1‘in sonraki düğümünü hesaplamak için list2‘yi ve list1‘in sonraki düğümlerini kullanarak hesaplama yap.
Eğer list2‘deki değer list1‘deki değerden küçük ise list2‘in sonraki düğümünü hesaplamak için list1‘i ve list2‘in sonraki düğümlerini kullanarak hesaplama yap.

Bu mantığın kodu da aşağıdaki gibi olacaktır.

public ListNode MergeTwoLists(ListNode list1, ListNode list2) 
    {

        if(list1 == null) return list2;
        if(list2 == null) return list1;
        if(list1.val <= list2.val)
        {
            list1.next = MergeTwoLists(list1.next,list2);
            return list1;
        }
        else
        {
            list2.next = MergeTwoLists(list1,list2.next);
            return list2;
        }
}

Umarım açıklayıcı olmuştur. Herkese iyi çalışmalar dilerim.