Leetcode 23 Merge k Sorted Lists

Soru

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Örnek 1

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Örnek 2

Input: lists = []
Output: []

Örnek 3

Input: lists = [[]]
Output: []

Çözüm

• “23. Merge k Sorted Lists” sorusu, birden fazla sıralı bağlı listenin tek bir sıralı bağlı listeye birleştirilmesini ister. Bu problem, verilen k sıralı bağlı listenin tüm elemanlarını içeren tek bir sıralı bağlı liste oluşturmayı gerektirir ve bu liste de sıralı olmalıdır.
• Girdi: ListNode türünde k tane sıralı bağlı listenin baş düğümleri (lists).
• Çıktı: Bu listelerin elemanlarını içeren tek bir sıralı bağlı liste.
• Bu problem birkaç farklı yöntemle çözülebilir:
• Min-Heap (Öncelikli Kuyruk) Kullanarak:
• Her listenin baş düğümünü bir min-heap’e ekleyin.
• Heap’ten en küçük düğümü çıkarın, sonuca ekleyin ve bu düğümün next düğümünü heap’e ekleyin.
• Bu işlemi tüm düğümler işlenene kadar devam ettirin.
• İki Listeyi Birleştirme Yöntemiyle:
• mergeTwoLists fonksiyonu kullanarak iki listeyi adım adım birleştirin.
• Bu işlemi tüm listeler tek bir liste kalana kadar devam ettirin.
• D&C (Böl ve Yönet) Yaklaşımı:
• Listenin ortasından bölün, iki yarıyı ayrı ayrı birleştirin.
• İki yarının sonuçlarını tekrar birleştirin.
• Çalışma Mekanizması:
• Heap İnitializasyonu: İlk olarak, her listenin baş düğümü (eğer boş değilse) bir heap’e (öncelikli kuyruk) eklenir.
• Düğüm Çıkarma ve Ekleme: En küçük düğüm heap’ten çıkarılır, sonuç listesine eklenir ve bu düğümün next elemanı, varsa, heap’e eklenir.
• Sonuç Oluşturma: Bu işlem, tüm düğümler işlenene kadar devam eder ve böylece tüm listeler tek bir sıralı liste olarak birleştirilir.

Code (Min-Heap Yöntemi Kullanılarak)

from heapq import heappush, heappop

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

class Solution:
    def mergeKLists(self, lists):
        head = point = ListNode(0)
        heap = []
        
        # Tüm listelerin baş düğümlerini heap'e ekleyin
        for lidx, l in enumerate(lists):
            if l:
                heappush(heap, (l.val, lidx, l))
        
        # En küçük elemanı bul ve listeye ekle, sonra bir sonraki düğümü heap'e ekle
        while heap:
            val, idx, node = heappop(heap)
            point.next = ListNode(val)
            point = point.next
            node = node.next
            if node:
                heappush(heap, (node.val, idx, node))
        
        return head.next

Complexity

• Time complexity (Zaman Karmaşıklığı): O(N log k), burada N toplam düğüm sayısı, k ise liste sayısıdır. Her düğüm için heap’e eklemek ve çıkarmak log k zaman alır.
• Space complexity (Alan Karmaşıklığı): O(k), min-heap’te her zaman en fazla k düğüm bulunur.