---

1. Problem Summary

You are given an array of k linked lists, where each list is:

• individually sorted in ascending order
• may be empty or contain any number of nodes

Your task is to merge all k linked lists into one single sorted linked list and return its head.

Example:

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

Output:
1→1→2→3→4→4→5→6

---

2. Key Insights

Insight 1: Naive concatenation then sort is inefficient

Concatenating and sorting results in:

O(N log N)

but loses benefits of sorted lists.

Insight 2: Merging pairwise repeatedly works but slower

Repeated merging k lists costs:

O(kN)

Insight 3: A min-heap (priority queue) efficiently extracts smallest head

By always pulling the smallest current node:

• we maintain global ordering
• insertion/removal in heap costs log k

Insight 4: Heap never holds more than k nodes

Each list contributes at most one node to heap at a time.

Insight 5: Supports lists of varying lengths seamlessly

When a node is removed, its next node is inserted if present.

---

3. Approach

Priority Queue (Min-Heap) merging

Steps:

1. Initialize a min-heap ordered by node value
2. Push the head of each non-null list into heap
3. Create a dummy head for result list
4. While heap not empty:
   • extract smallest node
   • append to result
   • if extracted node has next, insert into heap
5. Return merged list starting from dummy.next

---

4. Time and Space Complexity

Time Complexity:

O(N log k)

Where:

• N = total number of nodes across all lists
• k = number of lists

Reason:

• each node pushed and popped once
• heap operations cost log k

Space Complexity:

O(k)

Heap holds at most k nodes.

---

5. Java Solution

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> a.val - b.val
        );

        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();
            current.next = smallest;
            current = current.next;

            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }

        return dummy.next;
    }
}

---

6. Dry Run Examples

Example 1

Input:

[
  1→4→5,
  1→3→4,
  2→6
]

Heap initially:

1,1,2

Process sequence:

1 → from list1 (push 4)
1 → from list2 (push 3)
2 → from list3 (push 6)
3 → from list2 (push 4)
4 → from list1 (push 5)
4 → from list2
5 → from list1
6 → from list3

Output:

1→1→2→3→4→4→5→6

---

Example 2

Input:

[]

Output:

null

---

Example 3

Input:

[null, null, 5→7→9]

Output:

5→7→9

---

Example 4

Input:

[1, 0]

Output:

0→1

---

Example 5

Input:

[2→2→2, 2→2, 2]

Output:

2→2→2→2→2→2

---

7. Why This Solution Works

• always chooses globally smallest available node
• preserves sorted order automatically
• avoids full sorting
• avoids repeatedly scanning all list heads
• scales efficiently with large k

---

8. Common Mistakes

1. Merging lists pairwise in nested loops
2. Forgetting to check for null lists
3. Not advancing pointers correctly when appending
4. Losing reference to head (fixed with dummy node)
5. Using sorting on array of values instead of list nodes