LeetEye LeetEye
Medium Linked List ~5 min

Merge K Sorted Lists

linked-list merge-k-sorted-lists

Problem

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.

Examples

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

Use a min-heap to always pick the smallest among k candidates.

Min-heap of k heads: always pop smallest, push its next. O(N log k) — each node does one push and one pop.

How to Approach This Problem

Pattern Recognition: When you see keywords like merge k sorted lists linked-list, think Linked List.

Step-by-Step Reasoning

1 Merge lists one by one: merge(merge(merge(l1,l2),l3),l4)... Time complexity?
Answer: O(kN)
First merge is 2n, second is 3n, ..., total ≈ (2+3+...+k)n = O(kN).
2 Pair up lists and merge pairs, then repeat: Time complexity?
Answer: O(N log k)
log k levels of merging, each level processes all N nodes total.
3 Using a min-heap of size k helps because:
Answer: We can find minimum of k elements in O(log k)
Always extract minimum head in O(log k) instead of O(k) linear scan.
4 The heap should store:
Answer: Just the head of each non-empty list
We only need to compare current candidates (heads). After picking one, add its next to the heap.
5 For each of N nodes in the result:
Answer: One push and one pop
Pop the minimum, push its next (if exists). Both are O(log k).
6 N nodes, each requiring O(log k) heap operations:
Answer: O(N log k)
N × O(log k) = O(N log k).

Solution

import heapq

def mergeKLists(lists: List[ListNode]) -> ListNode:
    # Min heap: (value, index, node)
    heap = []
    
    # Add head of each non-empty list
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    
    dummy = ListNode()
    curr = dummy
    
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next

Complexity Analysis

Time O(N log k)
Space O(k)

Master This Pattern

Build intuition with interactive MCQs. Practice Linked List problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye