CP #8 : Add Two Numbers Problemi

Problem surada.

Cozum

Planimiz soyle: verilen linked list'leri sayiya cevirip, sayilari toplayip, tekrar linked liste'e cevirip geri dondurecegiz. 

Oncelikle sayiya cevirelim:

2 --> 4 --> 3

2'den baslayarak, elde edecegimiz deger 342 olmali. Yani 2 + 40 + 300.

Yani her adimda mevcut node degerini basamak carpani ile carpip toplayacagiz. Ve de basamak carpanini de 10 ile carparak guncelleyecegiz.

def toDecimal(node):

    ret = 0

    multiplier = 1

    cur = node

    # listenin sonuna kadar gidelim

    while cur:

        # her adimda basamak degerini hesapla ve toplama ekle

        ret += multiplier * cur.val

        # basamak degeri her adimda 10 kat artiyor

        multiplier *= 10

        # listeyi ilerletmeyi unutursak bu donguden cikamayiz

        cur = cur.next

    # sonucu dondur

    return ret

Daha sonra verilen bir sayisi tekrar linked liste'e donusturelim:

708 icin 8 --> 0 --> 7 seklinde bir linked list elde etmemiz gerekli. Sayiya sondan baslayabilmek icin, her adimda son basamagi almamiz gerekiyor. Bunu da modulus (mod) operatoru ile yapabiliriz. Bunu yaptiktan sonra da sayiyi 10'a bolerek (ama kalansiz), ilerlememiz gerekiyor.

708 % 10 --> 8

70 % 10 --> 0

7 % 10 --> 7

Seklinde linked listi olustacagiz.

def toLinkedList(value):

    # bos bir node ile baslayalim

    tail = ListNode(None, None)

    # biz surekli taile ekleyerek gidecegiz ama 

    # nihayetinde en bastaki node'u dondurmemiz gerek

    # o acidan head'e da bir referans tutacagiz

    head = tail

    

    # en sondaki basamak degerini almamiz gerek

    cur_digit = value % 10

    

    # ensondaki basamak degerini aldiktan sonra

    # sayiyi da ilerletmemiz gerekli    

    value = value // 10

    tail.val = cur_digit

    while value > 0:

        cur_digit = value % 10

        value = value // 10

        tail.next = ListNode(cur_digit, None)

        tail = tail.next

    return head

Bu iki fonksyionu implemente ettikten sonra getiye pek bisey kalmiyor zaten. Gene de baglamayi yapalim:

def addTwoNumbers(self, l1, l2):

    # ... 

    # fonk tanimlamalari

    val1 = toDecimal(l1)

    val2 = toDecimal(l2)

    retunr toLinkedList(val1 + val2)

Bu haliyla gonderdigim zaman leetcode kabul ediyor. 

Analiz

Verilen linked list'leri one pass seklinde itere ettigimiz icin lineer bir complexity'e sahibiz, O(n).

Bunun yaninda hafiza gereksinimi ise toDecimal icin sabit, O(1). Ama toLinkedList icin verilen input'a gore yine lineer olarak artmakta, O(n) seklinde olmaktadir.