Leetcode 021 Merge Two Sorted Lists

Soru

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Örnek 1

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Örnek 2

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

Örnek 3

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

Çözüm

• İki sıralı bağlı listeyi birleştirmenizi ve tek sıralı bir bağlı liste oluşturmanızı ister. Bu problem, iki sıralı bağlı listenin elemanlarını küçükten büyüğe doğru birleştirerek yeni bir sıralı liste oluşturmayı gerektirir.
• Girdi: İki sıralı tek yönlü bağlı liste başı l1 ve l2.
• Çıktı: l1 ve l2’nin elemanları ile oluşturulan yeni sıralı tek yönlü bağlı liste.
• Bu problem yinelemeli (iterative) veya özyinelemeli (recursive) yöntemlerle çözülebilir. Her iki yöntem de, iki listenin başlarından başlayarak karşılaştırmalar yapar ve daha küçük olan düğümü sonuç listesine ekler.
• Çalışma Mekanizması:
• Yinelemeli Yöntem:
• İki liste başından itibaren elemanları karşılaştırır.
• Daha küçük olan düğümü yeni listeye ekler ve ilgili listenin başını bir sonraki düğüme taşır.
• Karşılaştırma bittiğinde, kalan elemanları yeni listeye ekler.
• Özyinelemeli Yöntem:
• l1’in değeri l2’den büyükse, l1 ve l2 yer değiştirir.
• Daha küçük düğüm (l1), l1.next ile kendisinden sonra gelenleri özyinelemeli olarak birleştirmeye devam eder.

Code

• Yinelemeli Çözüm Python Kodu:

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

class Solution:
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode()  # Yeni liste için dummy baş düğüm
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        # Kalan elemanları ekleyin
        tail.next = l1 if l1 else l2

        return dummy.next

• Özyinelemeli Çözüm Python Kodu:

class Solution:
    def mergeTwoLists(self, l1, l2):
        if not l1 or (l2 and l1.val > l2.val):
            l1, l2 = l2, l1  # l1 her zaman daha küçük veya eşit elemanı göstermeli
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

Complexity

• Time complexity Zaman Karmaşıklığı: Her iki yöntem için de O(n+m), burada n ve m iki bağlı listenin uzunluklarıdır.
• Space complexity Alan Karmaşıklığı: Yinelemeli yöntem için O(1), çünkü ekstra alan kullanılmaz. Özyinelemeli yöntem için O(n+m), çünkü her çağrı için çağrı yığınında bir kayıt tutulur.