CP #5 : Merge Two Sorted Lists Problemi

Problem surada.

Cozum

Soruda verilen 2 linked list'i merge etmemiz isteniyor. Su sekilde ilerleyebiliriz:

1. Geri dondurecegimiz deger, olusturulan merge edilmis linked list'in head (yani baslangic) node'u olacak. Ancak biz merge islemi yaparken hep listenin sonuna ekleme yapacagiz. Bu durumda, sonuc listesine head ve tail olmak uzere 2 referans tutmak ismizi kolaylastiracaktir. 

1. Iki liste uzerinde iterasyon yapacagimiz icin, halihazirda okunan liste node'u tutacak 2 head referansi kullanacagiz. Bunlari iki tane serit okuyor gibi dusunebiliriz. Ya da kaset okuyucusu gibi. Her bir okuma yaptigimizda head'in degerini guncelleyecegiz. Ve liste bittigi zaman bu head degeri None olmus olacak.

2. Hangi liste uzerinde iterasyon yaparken, ikisinden birisi bittigi zaman donguye son verecegiz. Ve eger hala elemani bulunan bir liste var ise, onun tum elemanlarini sonuca ekleyebiliriz. 

3. Son olarak da en basta tuttugumuz sonuc head node'unu donduruyoruz. 

ret = None

tail = None

head1 = l1

head2 = l2

if head1.val < head2.val:

    ret = head1

    head1 = head1.next # okuma yaptik, head1'i ilerlet

else:

    ret = head2

    head2 = head2.next

tail = head # simdilik tail'de baska deger yok, dolayisi ile head'e esit

# listeleri itere etmeye baslayalim. her adimda sadece 1 listeden okuyor olacagiz, kucuk degere sahip olandan.

while head1 and head2:

    if head1.val < head2.val:

        tail.next = head1

        head1 = head1.next

    else:

        tail.next = head2

        head2 = head2.next

    # ekleme yaptigimiz icin taili de ilerletmemiz gerekiyor

    tail = tail.next 

# bu noktaya geldiysek listelerden birisi bitti

# ama hangisi bunu daha bilmiyoruz, ikisin de kontrol edip

# bitmeyendeki tum elemanlari artik rahatca sonuca ekleyebiliriz

if head1:

    while head1:

        tail.next = head1

        head1 = head1.next

        tail = tail.next

if head2:

    while head2:

        tail.next = head2

        head2 = head2.next

        tail = tail.next

return ret

Cok fazla kod duplikasyonu var, bu kisimlari refaktor edebiliriz. Bunun yaninda edge case'ler var. Ornegin verilen linked listlerden birisi None olabilir, bu durumda None olmayani direk dondurmemiz gerekiyor. Ikisi birden None olabilir, bu durumda da None dondurmemiz gerekiyor.

Kontrolleri de en basta yapiyorum:

if not l1 and not l2:

    return None

if not l1:

    return l2

if not l2:

    retun l1

Diger bir problemde gorusmek uzere.