k adet sıralı bağlı listeyi tek bir sıralı listede birleştirin (Merge k Sorted Lists).

En verimli yaygın çözüm min-heap kullanmaktır: heap'te her listenin o anki başı bulunur; en küçüğü çıkarıp sonuca ekler, aynı listenin bir sonraki düğümünü heap'e koyarız. Heap boyutu en fazla k olduğu için her işlem O(log k)'dir.

import heapq

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

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))  # i: eşitlikte karşılaştırma için
    dummy = tail = ListNode()
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Neden tuple'a i ekliyoruz?

İki düğümün değeri eşitse Python tuple'ın ikinci elemanını karşılaştırır. ListNode nesneleri karşılaştırılamadığı için TypeError alınır; benzersiz i bunu engeller.

Yaklaşımların karşılaştırması (N toplam düğüm)

Divide and conquer

İki sıralı listeyi birleştirme (Merge Two Sorted Lists) fonksiyonunu yazıp listeleri merge sort gibi çiftler halinde birleştirirsiniz; log k tur yapılır, her turda toplam N düğüm işlenir.

Gerçek hayattaki karşılığı

Veritabanlarında ve büyük veri işlemede external merge sort: belleğe sığmayan veri parçalar halinde sıralanıp diske yazılır, sonra k-way merge ile birleştirilir.