Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Merge K Sorted Lists

Merge K Sorted Lists

Master this topic with zero to advance depth.

Merge K Sorted Lists

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.

Visual Representation

lists = [ 1->4->5, 1->3->4, 2->6 ] Min-Heap State: 1. Insert heads: [1, 1, 2] 2. Extract 1, add next(4): Heap = [1, 2, 4] 3. Extract 1, add next(3): Heap = [2, 3, 4] 4. Extract 2, add next(6): Heap = [3, 4, 6]... Merged Result: 1->1->2->3->4->4->5->6
Hard

Examples

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

Level I: Brute Force (Array + Sort)

Intuition

The simplest approach is to ignore the linked list structure initially. We can traverse all the linked lists, collect all the values into an array, sort the array, and then build a new linked list from the sorted array.

⏱ O(N log N) where N is the total number of nodes💾 O(N) to store all values in the array and the new linked list

Detailed Dry Run

lists = [[1,4,5],[1,3,4],[2,6]]

  1. Collect: [1,4,5,1,3,4,2,6]
  2. Sort: [1,1,2,3,4,4,5,6]
  3. Build new list: 1->1->2->3->4->4->5->6
java
import java.util.*;

public class Main {
    public static ListNode mergeKLists(ListNode[] lists) {
        List<Integer> values = new ArrayList<>();
        for (ListNode list : lists) {
            while (list != null) {
                values.add(list.val);
                list = list.next;
            }
        }
        Collections.sort(values);
        
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int val : values) {
            current.next = new ListNode(val);
            current = current.next;
        }
        return dummy.next;
    }
}

⚠️ Common Pitfalls & Tips

O(N log N) time and O(N) space. Not optimal for large lists.

Visual Trace

Lists: [1->4, 1->3] 1. Array: [1, 4, 1, 3] 2. Sorted: [1, 1, 3, 4] 3. Linked: 1 -> 1 -> 3 -> 4
Approach 2

Level II: Divide and Conquer

Intuition

Merge lists in pairs, decreasing the number of lists by half in each step. This is more efficient than merging one by one and avoids the overhead of a Min-Heap if k is small.

Visual Trace

[L1, L2, L3, L4] \ / \ / [L12] [L34] \ / [Final]
⏱ O(N log K)💾 O(log K) recursion

Detailed Dry Run

Lists = [L1, L2, L3, L4]. 1. Merge(L1, L2)=L12, Merge(L3, L4)=L34. 2. Merge(L12, L34) = Result.

java
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int left, int right) {
    if (left == right) return lists[left];
    int mid = left + (right - left) / 2;
    ListNode l1 = merge(lists, left, mid);
    ListNode l2 = merge(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } 
        else { tail.next = l2; l2 = l2.next; }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Deep recursion could cause stack overflow in some environments, though log(k) is usually safe.

Approach 3

Level III: Min-Heap (Optimal)

Intuition

Use a Min-Heap (Priority Queue) to always extract the smallest current node among the heads of all k lists.

⏱ O(N log K) where N is total nodes and K is the number of lists💾 O(K) for the Min-Heap

Detailed Dry Run

lists = [[1,4,5], [1,3,4], [2,6]]

  1. Heap: [(1: from L1), (1: from L2), (2: from L3)]
  2. Pop 1 (L1). Res: [1]. Push 4 (L1). Heap: [1, 2, 4]
  3. Pop 1 (L2). Res: [1,1]. Push 3 (L2). Heap: [2, 3, 4]...
java
public class Main {
    public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) minHeap.add(node);
        }
        ListNode dummy = new ListNode(0), tail = dummy;
        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();
            tail.next = smallest;
            tail = tail.next;
            if (smallest.next != null) minHeap.add(smallest.next);
        }
        return dummy.next;
    }
}

⚠️ Common Pitfalls & Tips

In Python, using a tie-breaker like i or a wrapper is necessary for heapq when values are equal.

← Previous QuestionPartition List
Next Question →Reverse Nodes in k-Group