Merge Multiple Sorted Linked Lists Efficiently with a Min‑Heap

Problem description: Given an array of sorted linked lists (each list is already in ascending order), merge all the lists into a single sorted linked list and return its elements.

Input: The first line contains n, the number of linked lists. The next n lines each contain the elements of one list separated by spaces.

Output: All elements of the merged linked list in ascending order.

Example

3
1 4 5
1 3 4
2 6

1 1 2 3 4 4 5 6

Note: This problem is identical to LeetCode 23 – Merge k Sorted Lists.

Two practical approaches are possible:

Directly perform a k‑way merge on the sorted arrays.

Convert each array to a linked list and then perform a k‑way merge on the linked lists.

Using a min‑heap (priority queue) is recommended for both approaches because it efficiently keeps track of the smallest current element among the k structures.

Solution 1 – Linked‑list implementation (Python)

# 题目：【链表】大疆2023秋招-链表合并
# 作者：闭着眼睛学数理化
# 算法：链表/优先队列

import heapq

# Define a linked‑list node
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Build a linked list from an array (reverse order for simplicity)
def build_linked_list(nums):
    nxt_node = None
    for num in nums[::-1]:
        node = ListNode(num, nxt_node)
        nxt_node = node
    return node

# Print linked list values
def print_linked_list(head):
    node = head
    res = []
    while node:
        res.append(node.val)
        node = node.next
    print(" ".join(str(v) for v in res))

# Merge k sorted linked lists using a min‑heap
def mergeKLists(lists):
    heap = [(node.val, i) for i, node in enumerate(lists) if node]
    heapq.heapify(heap)
    dummy = ListNode(0)
    cur = dummy
    while heap:
        _, idx = heapq.heappop(heap)
        cur.next = lists[idx]
        cur = cur.next
        lists[idx] = lists[idx].next
        if lists[idx]:
            heapq.heappush(heap, (lists[idx].val, idx))
    return dummy.next

k = int(input())
lists = []
for _ in range(k):
    nums = list(map(int, input().split()))
    lists.append(build_linked_list(nums))

merged_head = mergeKLists(lists)
print_linked_list(merged_head)

Solution 2 – Array implementation (Python)

# 题目：【链表】大疆2023秋招-链表合并
# 作者：闭着眼睛学数理化
# 算法：数组/优先队列

import heapq

# Merge k sorted arrays using a min‑heap
def mergeKLists(lists):
    heap = [(arr[0], i) for i, arr in enumerate(lists) if arr]
    heapq.heapify(heap)
    idx_ptr = [0] * len(lists)
    result = []
    while heap:
        val, i = heapq.heappop(heap)
        result.append(val)
        idx_ptr[i] += 1
        if idx_ptr[i] < len(lists[i]):
            heapq.heappush(heap, (lists[i][idx_ptr[i]], i))
    return result

k = int(input())
lists = []
for _ in range(k):
    nums = list(map(int, input().split()))
    lists.append(nums)

merged = mergeKLists(lists)
print(" ".join(str(v) for v in merged))

Time and Space Complexity

Time complexity: O(k N log k), where k is the number of lists and N is the total number of elements. Each element is inserted into and removed from the heap once, and heap operations cost O(log k).

Space complexity: O(k) for the heap, which stores at most one element from each list at any time.