LeetCode #2: İki Sayıyı Bağlı Listelerle Toplama Rehberi

LeetCode’da sıkça karşılaşılan ve algoritmik düşünme becerilerini geliştiren klasik bir problem olan “Add Two Numbers” (İki Sayıyı Topla) konusunu ele alıyoruz. Bu makale, bağlı listelerle büyük sayıları toplama yöntemini sıfırdan adım adım açıklayacak ve gerçek dünya uygulamalarına değinecek.

Bilgisayarların dünyasında sayılarla çalışmak temel bir işlemdir. Ancak, standart veri tiplerinin temsil edebileceği sayı büyüklüklerinin bir sınırı vardır. Örneğin, 64-bit bir tam sayı (long long) bile belli bir değere kadar sayıyı saklayabilir. Peki ya milyonlarca basamağı olan devasa sayıları toplamanız gerekirse ne yaparsınız? İşte LeetCode #2 problemi tam olarak bu senaryoya bir çözüm sunar ve sizi bu tür büyük sayıları efektif bir şekilde işlemek için bağlı listeler gibi veri yapılarını kullanmaya iter.

Bu problemde, her bir basamağı ayrı bir bağlı liste düğümünde ters sırada saklanmış iki adet boş olmayan sayıyı toplamanız istenir. Örneğin, (2 -> 4 -> 3) listesi 342 sayısını, (5 -> 6 -> 4) listesi ise 465 sayısını temsil eder. Bu iki sayının toplamı olan 807, (7 -> 0 -> 8) olarak temsil edilmelidir. Burada dikkat edilmesi gereken en önemli nokta, basamakların ters sırada olmasıdır. Yani, bağlı listenin başı sayının birler basamağını, bir sonraki düğüm onlar basamağını ve bu şekilde devam eder.

Bu problemin önemi sadece bir LeetCode sorusunu çözmekle sınırlı değildir; bilgisayar bilimlerinde “keyfi hassasiyet aritmetiği” (arbitrary precision arithmetic) adı verilen daha geniş bir kavramın temelini oluşturur. Finansal sistemlerde, kriptografide, bilimsel hesaplamalarda veya uzay araştırmalarında, standart veri tiplerinin kapasitesini aşan hassasiyete veya büyüklüğe sahip sayılarla çalışmak sıkça karşılaşılan bir durumdur. İşte bu tür durumlarda, sayıları basamak basamak temsil etmek ve bu basamaklar üzerinde işlem yapmak hayati önem taşır. Bağlı listeler, bu dinamik büyüklükteki sayıları temsil etmek için doğal ve esnek bir yol sunar, zira ihtiyaca göre düğümler ekleyebilir veya çıkarabilirsiniz. Böylece, bellekte sabit bir yer ayırma kısıtlamasına takılmadan istediğiniz kadar büyük sayılarla işlem yapabilirsiniz.

Gerçek Dünya Senaryosu: Büyük Sayıların Yönetimi

Günümüzde finans sektöründeki algoritmik ticaret sistemlerini veya kripto para birimlerinin blok zincir teknolojisini düşünün. Bu sistemler, yüksek hassasiyet gerektiren milyarlarca veya trilyonlarca basamaklı işlemleri yönetmek zorundadır. Örneğin, bir bankanın faiz hesaplamaları, kur farkları veya döviz kuru işlemleri çok küçük ondalık değerlere kadar hassas olmak zorundadır. Standart double veya float tipleri yuvarlama hatalarına neden olabilirken, bağlı listelerle temsil edilen sayılar, her bir basamağı ayrı ayrı ele alarak bu tür hataları ortadan kaldırır. Bilimsel simülasyonlarda veya astronomik hesaplamalarda da benzer şekilde çok büyük veya çok küçük sayıların hassas bir şekilde temsil edilmesi ve üzerinde işlem yapılması esastır. Bu tür senaryolarda, LeetCode #2’nin arkasındaki mantık, bu karmaşık ve kritik hesaplamalar için temel bir yapı taşı sağlar.

Temel Kavramlar: Bağlı Listeler ve Düğümler Nasıl Çalışır?

LeetCode #2 problemini etkili bir şekilde çözebilmek için bağlı listelerin (Linked Lists) temel yapısını ve işleyişini iyi anlamak oldukça önemlidir. Bağlı liste, doğrusal bir veri yapısıdır; ancak dizilerden farklı olarak, elemanlar bellekte ardışık olarak depolanmaz. Bunun yerine, her eleman, “düğüm” (node) adı verilen ayrı bir nesne olarak saklanır ve bir sonraki elemanın bellek adresini (bir “işaretçi” veya “referans”) içerir. Bu yapı, bağlı listeleri dinamik boyutlu ve esnek kılar.

Her bağlı liste düğümü tipik olarak iki ana bölümden oluşur:

• Değer (val): Düğümün depoladığı gerçek veri. Bu problemde, bu değer sayının bir basamağını temsil eder (0-9 arası bir sayı).
• Sonraki Düğüm İşaretçisi (next): Listenin bir sonraki düğümüne referans veren bir işaretçi. Eğer düğüm listenin son elemanıysa, bu işaretçi genellikle null veya None değerini alır.

LeetCode #2 bağlamında, her bağlı liste bir sayıyı temsil ederken, her düğüm bu sayının bir basamağını saklar. Problemin spesifikasyonuna göre, basamaklar tersten sıralanmıştır. Yani, bağlı listenin başı (head) sayının birler basamağını, head.next onlar basamağını ve bu şekilde devam eder. Bu ters sıra, toplama işlemini geleneksel elden toplama yöntemine çok benzer hale getirir, çünkü birler basamağından başlayarak sola doğru ilerleriz. Bu yaklaşım, sayıların basamakları üzerinde doğrudan işlem yapmamızı sağlayarak büyük sayıların yönetimini kolaylaştırır.

LeetCode #2 Problem Tanımı: Tam Olarak Ne İsteniyor?

LeetCode’daki tam problem tanımı şu şekildedir: “Sırasıyla boş olmayan iki bağlı liste olarak temsil edilen iki negatif olmayan tam sayıyı toplayın. Sayıların basamakları ters sırada saklanır ve her düğüm yalnızca tek bir basamak içerir. İki sayının toplamı olan yeni bir bağlı liste döndürün. İki sayının da baştaki sıfırlar içermediğini varsayabilirsiniz, ancak sayının kendisi 0 olabilir.” Örneğin, l1 = [2,4,3] ve l2 = [5,6,4] girdileri için çıktı [7,0,8] olmalıdır. Bu, 342 + 465 = 807 anlamına gelir. Bu ters sıra, basamak basamak toplamayı, tıpkı ilkokulda öğrendiğimiz gibi, sağdan sola doğru (yani listede baştan sona) yapmamızı sağlar, bu da algoritmayı basitleştirir.

Çözüm Yaklaşımı: İki Bağlı Listeyi Adım Adım Nasıl Toplarız?

İki sayıyı temsil eden bağlı listeleri toplarken, temel mantık aslında ilkokulda öğrendiğimiz elden toplama işlemine çok benzer. Sağdan sola doğru (yani bağlı listelerde baştan sona) basamakları toplarız ve bir basamak 9’u aşarsa “elde” (carry) bir sonraki basamağa aktarılır. Bu algoritma, bir döngü içinde, her iki listeyi aynı anda veya birinin sonuna ulaşıldığında diğerini tek başına işleyerek ilerler.

Çözüm için adım adım bir plan şöyle oluşturulabilir:

1. Yardımcı (Dummy) Düğüm Oluşturma: Toplamı saklayacak yeni bir bağlı liste oluşturmak için bir “yardımcı baş düğüm” (dummyHead) kullanmak yaygın ve iyi bir pratikttir. Bu düğümün amacı, gerçek toplam listemizin başlangıcını belirgin bir şekilde işaretlemektir. Böylece, toplam listeyi oluştururken ilk düğümü özel olarak ele almak zorunda kalmayız. Daha sonra bu dummyHead‘in next işaretçisi, asıl sonuç listemizin başı olacaktır. Ayrıca, mevcut düğümü takip etmek için bir current işaretçisi tutarız.
2. Elde Değişkeni (Carry): Toplama işlemi sırasında oluşan elde değerini (0 veya 1 olabilir) takip etmek için carry adında bir değişken tanımlarız. Başlangıçta carry değeri 0 olacaktır.
3. Döngü ile Toplama: İki listeyi eş zamanlı olarak veya bir liste bitene kadar döngü ile gezeriz. Döngü şu koşullardan biri doğru olduğu sürece devam eder:
   • İlk liste (l1) henüz bitmemişse.
   • İkinci liste (l2) henüz bitmemişse.
   • carry değeri hala 1 ise (yani son bir elde değeri kalmışsa).
4. Basamakları Toplama: Her döngü adımında, mevcut l1 ve l2 düğümlerinin değerlerini (eğer null değillerse) ve mevcut carry değerini toplarız. Eğer bir liste bitmişse, o listenin değeri olarak 0 kabul edilir. Bu toplam, sum adında bir değişkende saklanır.
5. Yeni Basamak ve Elde Hesaplama: sum değerinden, yeni bağlı liste için basamağı (sum % 10) ve bir sonraki adım için elde değerini (sum // 10) hesaplarız. Yeni basamağı içeren bir düğüm oluşturur ve bunu current düğümünün next‘i olarak ekleriz. Ardından current işaretçisini yeni eklenen bu düğüme kaydırırız.
6. Liste İşaretçilerini İlerletme: l1 ve l2 işaretçilerini, eğer null değillerse, bir sonraki düğüme ilerletiriz.
7. Sonuç Döndürme: Döngü bittiğinde, dummyHead.next bizim aradığımız toplam listeyi döndürecektir.

Bu yaklaşım, liste uzunlukları farklı olduğunda bile sorunsuz çalışır, çünkü biten listenin basamakları için 0 değeri kullanılır. Ayrıca, en son basamaklar toplandıktan sonra bile elde değeri 1 kalmışsa (örneğin 99 + 1 = 100 işleminde), döngü bu son eldeyi de yeni bir düğüm olarak ekleyerek doğru sonucu elde etmemizi sağlar. Bu yöntem, bilgisayarların büyük sayıları manuel toplama yöntemine benzer şekilde işlemesini sağlayan zarif ve verimli bir yoldur.

Algoritmanın Temel Adımları: Eldeyi Takip Etmek

Elde (carry) değeri, bu algoritmanın kalbidir. Her basamak toplandığında, eğer toplam 9’dan büyükse, elde değeri 1 olur ve bu değer bir sonraki basamak toplamına eklenir. Örneğin, 3 + 4 = 7 olduğunda carry 0’dır. Ancak, 6 + 8 = 14 olduğunda, yeni basamak 4 olur ve carry 1 olarak bir sonraki basamağa aktarılır. Bu carry‘nin doğru bir şekilde yönetilmesi, sonucun doğruluğu için kritik öneme sahiptir. Döngü, tüm basamaklar işlense bile, carry hala 1 ise devam etmelidir; bu, toplama sonucunda orijinal listelerden daha uzun bir liste oluşabileceği anlamına gelir (örneğin 99 + 1 = 100, burada 100, iki basamaklı sayılardan daha fazla basamağa sahiptir). Bu son eldeyi eklemek, doğru sonucu garantiler.

Uygulamalı Kod: LeetCode #2 Çözümü Python ile

Şimdi yukarıda bahsettiğimiz çözüm yaklaşımını Python koduyla somutlaştıralım. Öncelikle, bağlı liste düğümlerini temsil edecek ListNode sınıfımızı tanımlamamız gerekiyor. Ardından, addTwoNumbers fonksiyonunu adım adım oluşturacağız. Python, bağlı liste düğümleri için referansları doğal bir şekilde yönetir, bu da kod yazımını oldukça sezgisel hale getirir.

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # Toplam listesinin başlangıcını işaretlemek için bir dummy (sahte) baş düğüm oluştur.
        # Bu, ilk düğümü özel olarak ele alma ihtiyacını ortadan kaldırır.
        dummyHead = ListNode(0)
        
        # Mevcut düğümü takip etmek için bir işaretçi. Başlangıçta dummyHead'i gösterir.
        current = dummyHead
        
        # Elde değerini saklamak için değişken.
        carry = 0

        # l1, l2 veya elde değeri 0'dan büyük olduğu sürece döngüyü sürdür.
        # Bu, tüm basamakların ve son elde değerinin işlenmesini sağlar.
        while l1 is not None or l2 is not None or carry != 0:
            # l1'den mevcut basamağı al. Eğer l1 bitmişse (None), 0 kullan.
            val1 = l1.val if l1 is not None else 0
            
            # l2'den mevcut basamağı al. Eğer l2 bitmişse (None), 0 kullan.
            val2 = l2.val if l2 is not None else 0

            # Mevcut basamakları ve eldeyi topla.
            total_sum = val1 + val2 + carry

            # Yeni elde değerini hesapla (toplamın 10'a bölümünün tam kısmı).
            carry = total_sum // 10
            
            # Yeni düğümün değerini hesapla (toplamın 10'a bölümünden kalan).
            digit = total_sum % 10

            # Yeni basamak değeriyle bir düğüm oluştur ve onu mevcut düğümün 'next'i yap.
            current.next = ListNode(digit)
            
            # Mevcut işaretçiyi yeni oluşturulan düğüme ilerlet.
            current = current.next

            # l1 ve l2 işaretçilerini bir sonraki düğüme ilerlet (eğer mevcutlarsa).
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next
        
        # Dummy baş düğümün bir sonraki düğümünü döndür, bu gerçek toplam listesidir.
        return dummyHead.next
    

Örnek Bir Uygulama: Kodu Çalıştırmak

Yukarıdaki kodu bir örnekle test edelim. Diyelim ki şu sayıları toplamak istiyoruz:

• l1: 342 (2 -> 4 -> 3 olarak temsil edilir)
• l2: 465 (5 -> 6 -> 4 olarak temsil edilir)

Beklenen sonuç: 807 (7 -> 0 -> 8 olarak temsil edilir)

Adım adım çalışmayı inceleyelim:

1. Başlangıç: dummyHead = ListNode(0), current = dummyHead, carry = 0.
2. 1. İterasyon (Birler Basamağı):
   • val1 = 2, val2 = 5.
   • total_sum = 2 + 5 + 0 = 7.
   • carry = 7 // 10 = 0.
   • digit = 7 % 10 = 7.
   • current.next = ListNode(7). current şimdi 7 düğümünü gösterir.
   • l1 4'e, l2 6'ya ilerler.
3. 2. İterasyon (Onlar Basamağı):
   • val1 = 4, val2 = 6.
   • total_sum = 4 + 6 + 0 = 10.
   • carry = 10 // 10 = 1.
   • digit = 10 % 10 = 0.
   • current.next = ListNode(0). current şimdi 0 düğümünü gösterir.
   • l1 3'e, l2 4'e ilerler.
4. 3. İterasyon (Yüzler Basamağı):
   • val1 = 3, val2 = 4.
   • total_sum = 3 + 4 + 1 = 8 (önceki iterasyondan gelen elde 1).
   • carry = 8 // 10 = 0.
   • digit = 8 % 10 = 8.
   • current.next = ListNode(8). current şimdi 8 düğümünü gösterir.
   • l1 None'a, l2 None'a ilerler.
5. Döngü Sonu: Hem l1 hem de l2 None oldu, carry 0 oldu. Döngü biter.
6. Sonuç: dummyHead.next döndürülür, bu da 7 -> 0 -> 8 listesini temsil eder.

Performans ve Optimizasyon: Daha Etkin Çözümler Mümkün Mü?

Algoritmik problemlerin çözümünde kodun doğruluğu kadar, performans analizi de büyük önem taşır. Çözümümüzün zaman ve uzay karmaşıklığı (Time and Space Complexity) bu bağlamda incelenmelidir. LeetCode #2 problemindeki bağlı listelerle toplama çözümü, verilen kısıtlamalar altında oldukça verimli bir yaklaşımdır.

Zaman ve Uzay Karmaşıklığı Analizi

• Zaman Karmaşıklığı (Time Complexity): Algoritma, her iki bağlı listeyi de baştan sona tek bir geçişte işler. En kötü durumda, her iki listedeki tüm düğümlerden (basamaklardan) bir kez geçeriz. Eğer l1'in uzunluğu m ve l2'nin uzunluğu n ise, döngü max(m, n) defa çalışacaktır. Her iterasyonda sabit sayıda işlem (toplama, bölme, mod alma, yeni düğüm oluşturma) yapılır. Dolayısıyla, zaman karmaşıklığı O(max(m, n))'dir. Bu, listelerin uzunluğu arttıkça çalışma süresinin doğrusal olarak artacağı anlamına gelir ve optimaldir çünkü tüm basamakları en az bir kez görmek zorundayız.
• Uzay Karmaşıklığı (Space Complexity): Çözümümüz, iki sayının toplamını tutmak için yeni bir bağlı liste oluşturur. Bu yeni listenin uzunluğu, en fazla max(m, n) + 1 olabilir (son bir elde durumu için). Bu nedenle, oluşturulan yeni düğüm sayısı listelerin uzunluğuna bağlıdır. Uzay karmaşıklığı da O(max(m, n))'dir. Bu da optimaldir, çünkü toplam sonucunu saklamak için bu kadar alana ihtiyacımız vardır.

Bu problem için daha etkin bir çözüm bulmak zordur çünkü zaten tüm basamakları okumak ve toplam basamakları depolamak zorundayız. Bazı dillerde (Python gibi) tamsayılar keyfi hassasiyeti destekler, yani sayı ne kadar büyük olursa olsun direkt toplama işlemi yapılabilir. Ancak LeetCode #2, bu özelliği kullanarak problemi çözmemizi istemez; bağlı listelerle algoritmayı kendimiz uygulamamızı bekler. Bu nedenle, bağlı liste düğümlerini sayılara dönüştürmek, toplamak ve sonra tekrar bağlı listeye dönüştürmek gibi yaklaşımlar genellikle hem karmaşıklığı artırır hem de çok büyük sayılar için bellekte aşırı yer kaplayabilir veya performans sorunlarına yol açabilir.

Performans açısından dikkat edilmesi gereken tek nokta, döngü içindeki gereksiz işlemlerden kaçınmaktır. Mevcut çözüm, her iterasyonda yalnızca temel aritmetik işlemleri ve referans güncellemelerini içerdiği için zaten oldukça verimlidir. Bu bağlamda, kodumuz verilen kısıtlamalar altında pratik olarak en iyi performansı sunar.

Mobil Uyumlu HTML Sunumu: Kod Bloklarınızı Nasıl Gösterirsiniz?

Teknik makalelerde kod blokları, içeriğin anlaşılması için hayati öneme sahiptir. Ancak farklı cihazlarda, özellikle küçük ekranlı mobil cihazlarda, bu kod bloklarının okunabilirliğini sağlamak kritik bir tasarım kararıdır. HTML ve CSS kullanarak bu uyumluluğu kolayca sağlayabiliriz. Makalemizin başında yer alan