Leetcode 002 Add Two Numbers

Soru

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Örnek 1

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Örnek 2

Input: l1 = [0], l2 = [0]
Output: [0]

Örnek 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Çözüm

• İki bağlı liste olarak temsil edilen iki sayıyı toplamanızı ister. Bu bağlı listeler, ters çevrilmiş sırayla sayıların basamaklarını tutar; yani, her liste başındaki düğüm bir sayının en düşük basamağını temsil eder ve her düğüm tek bir basamak tutar. Sorunun amacı, bu iki sayının toplamını aynı şekilde ters çevrilmiş bir bağlı liste olarak döndürmektir.
• Girdi: İki bağlı liste baş düğümü l1 ve l2. Her düğüm, bir tam sayı değer (0 ile 9 arası) tutar ve her liste en az bir düğüm içerir.
• Çıktı: İki sayının toplamını temsil eden, yeni bir ters çevrilmiş bağlı liste.
• Bu problemi çözmek için, iki liste üzerinde bir işaretçi kullanarak basamak basamak ilerler ve gerekirse taşıma (carry) uygularsınız. Yeni oluşturulan listenin her düğümü, karşılık gelen basamakların toplamını (ve varsa bir önceki taşımayı) içerir.
• Çalışma Mekanizması:
• Başlangıç Koşulları: dummy düğüm başlatılır ki, bu yeni oluşturulan sonucun başlangıcını işaret eder. current işaretçisi bu liste üzerinde hareket eder.
• Toplama ve Taşıma Yönetimi: Her iterasyonda, l1 ve l2den değerler alınır (liste sonunda yoksa 0 alınır). Bu değerler ve bir önceki taşımadan gelen değer toplanır. Toplamın 10’a bölümünden taşıma elde edilir ve kalan yeni basamak değeri olur.
• Liste İlerlemesi: İki liste de None olana kadar veya taşıma 0 olana kadar işlem devam eder.
• Sonuç: dummy.next, sonuç listesinin başını gösterir, çünkü dummy sadece başlangıç için kullanılan geçici bir düğümdür.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)  # Sonuç listesi için dummy başlangıç düğümü
        current = dummy
        carry = 0

        # l1 ve l2'nin sonuna kadar veya taşıma bitene kadar döngü
        while l1 or l2 or carry:
            val1 = (l1.val if l1 else 0)
            val2 = (l2.val if l2 else 0)
            
            # Yeni basamağın toplamı ve yeni taşıma
            total = val1 + val2 + carry
            carry = total // 10
            total = total % 10
            
            current.next = ListNode(total)
            current = current.next
            
            # İşaretçileri ilerlet
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        return dummy.next

Complexity

• Time complexity (Zaman Karmaşıklığı): O(max(n, m)), burada n ve m, l1 ve l2 uzunluklarıdır. En kötü durumda her iki liste de tamamen taranır.
• Space complexity (Alan Karmaşıklığı): O(max(n, m)), yeni bir liste oluşturulduğu için, en kötü durumda girdi listeleri kadar uzun olabilir.