Merge k Sorted Lists

Definition for Singly-linked List

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

Solution

Let $n$ be the total number of nodes, and $k$ be the number of sorted lists.

Complexity

time: $O(n \log(k))$
space: $O(1)$

Compare 1 by 1 using Priority Queue

from heapq import heappush, heappop

class HeapNode:
    def __init__(self, node):
        self.node = node
    
    def __lt__(self, other):
        return self.node.val < other.node.val

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        for idx, node in enumerate(lists):
            if node:
                heappush(heap, HeapNode(node))
        
        head = ListNode()
        curr = head
        while heap:
            node = heappop(heap).node
            # add node to list
            curr.next = node
            # update curr pointer
            curr = curr.next
            # add node.next to the heap
            if node.next:
                heappush(heap, HeapNode(node.next))
        return head.next

Merge with Divide and Conquer

def merge2Lists(self, l1, l2):
    head = curr = ListNode(-1)
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    
    if not l1:
        curr.next = l2
    elif not l2:
        curr.next = l1
    
    return head.next

def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    n = len(lists)
    if n == 0:
        return None
    interval = 1
    while interval < n:
        for i in range(0, n - interval, interval * 2):
            lists[i] = self.merge2Lists(lists[i], lists[i + interval])
        interval *= 2
    return lists[0]