Merge K Sorted Linked Lists

Problem Statement

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

Return the sorted linked list that is the result of merging all of the individual linked lists.

Example 1:

Input: lists = [[1,2,4],[1,3,5],[3,6]]
Output: [1,1,2,3,3,4,5,6]

Example 2:

Input: lists = []
Output: []

Example 3:

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

Constraints:

0 <= lists.length <= 1000
0 <= lists[i].length <= 100
-1000 <= lists[i][j] <= 1000

You should aim for a solution as good or better than O(n * k) time and O(1) space, where k is the total number of lists and n is the total number of nodes across all lists.

Recommended Time and Space Complexity

You should aim for a solution as good or better than O(n * k) time and O(1) space, where k is the total number of lists and n is the total number of nodes across all lists.

Hint 1

A brute-force solution would involve storing all n nodes in an array, sorting them, and converting the array back into a linked list, resulting in an O(nlogn) time complexity. Can you think of a better way? Perhaps consider leveraging the idea behind merging two sorted linked lists.

Hint 2

We can merge two sorted linked lists without using any extra space. To handle k sorted linked lists, we can iteratively merge each linked list with a resultant merged list. How can you implement this?

Hint 3

We iterate through the list array with index i, starting at i = 1. We merge the linked lists using merge_two_lists(lists[i], lists[i - 1]), which returns the head of the merged list. This head is stored in lists[i], and the process continues. Finally, the merged list is obtained at the last index, and we return its head.

Solution

Brute Force

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    nodes = []
    for lst in lists:
        while lst:
            nodes.append(lst.val)
            lst = lst.next
    nodes.sort()

    res = ListNode(0)
    cur = res
    for node in nodes:
        cur.next = ListNode(node)
        cur = cur.next
    return res.next

Time complexity: O(n log n) Space complexity: O(n)

Iteration

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    res = ListNode(0)
    cur = res

    while True:
        min_node = -1
        for i in range(len(lists)):
            if not lists[i]:
                continue
            if min_node == -1 or lists[min_node].val > lists[i].val:
                min_node = i

        if min_node == -1:
            break
        cur.next = lists[min_node]
        lists[min_node] = lists[min_node].next
        cur = cur.next

    return res.next

Time complexity: O(n * k) Space complexity: O(1)

Merge Lists One By One

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if len(lists) == 0:
        return None

    for i in range(1, len(lists)):
        lists[i] = merge_list(lists[i - 1], lists[i])

    return lists[-1]

def merge_list(l1, l2):
    dummy = ListNode()
    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
    if l1:
        tail.next = l1
    if l2:
        tail.next = l2
    return dummy.next

Time complexity: O(n * k) Space complexity: O(1)

Heap

import heapq
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class NodeWrapper:
    def __init__(self, node):
        self.node = node

    def __lt__(self, other):
        return self.node.val < other.node.val

def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if len(lists) == 0:
        return None

    res = ListNode(0)
    cur = res
    min_heap = []

    for lst in lists:
        if lst is not None:
            heapq.heappush(min_heap, NodeWrapper(lst))

    while min_heap:
        node_wrapper = heapq.heappop(min_heap)
        cur.next = node_wrapper.node
        cur = cur.next

        if node_wrapper.node.next:
            heapq.heappush(min_heap, NodeWrapper(node_wrapper.node.next))

    return res.next

Time complexity: O(n log k) Space complexity: O(k)

Divide And Conquer (Recursion)

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    if not lists or len(lists) == 0:
        return None
    return divide(lists, 0, len(lists) - 1)

def divide(lists, l, r):
    if l > r:
        return None
    if l == r:
        return lists[l]
    mid = l + (r - l) // 2
    left = divide(lists, l, mid)
    right = divide(lists, mid + 1, r)
    return conquer(left, right)

def conquer(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    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 l1:
        curr.next = l1
    else:
        curr.next = l2
    return dummy.next

Time complexity: O(n log k) Space complexity: O(log k)

Divide And Conquer (Iteration)

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if not lists or len(lists) == 0:
        return None

    while len(lists) > 1:
        merged_lists = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if (i + 1) < len(lists) else None
            merged_lists.append(merge_list(l1, l2))
        lists = merged_lists
    return lists[0]

def merge_list(l1, l2):
    dummy = ListNode()
    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
    if l1:
        tail.next = l1
    if l2:
        tail.next = l2
    return dummy.next

Time complexity: O(n log k) Space complexity: O(k)