23. Merge K Sorted Lists - Detailed Explanation

Problem Statement

Description:
You are given an array of k linked lists, where each linked list is sorted in ascending order. Your task is to merge all these linked lists into one sorted linked list and return its head.

Key Details:

• Each linked list is sorted.
• You must merge all lists so that the final list is sorted in ascending order.

Example Inputs, Outputs, and Explanations:

1. Example 1:

   • Input: lists = [[1,4,5], [1,3,4], [2,6]]
   • Output: [1,1,2,3,4,4,5,6]
   • Explanation:
     • The first list is 1->4->5, the second is 1->3->4, and the third is 2->6.
     • When merged in sorted order, the list becomes: 1->1->2->3->4->4->5->6.

2. Example 2:

   • Input: lists = []
   • Output: []
   • Explanation:
     • No linked lists are provided, so the result is an empty list.

3. Example 3:

   • Input: lists = [[]]
   • Output: []
   • Explanation:
     • There is one linked list, but it is empty. The merged list is also empty.

Constraints:

• The number of linked lists, k, can range from 0 to a large number.
• The total number of nodes across all lists is N.
• The lists may contain duplicate values.

Hints to Approach the Solution

1. Efficiently Finding the Minimum:

   • Since each list is already sorted, the smallest element among the lists is always one of the heads. How can you quickly find the smallest head?

2. Using Data Structures:

   • Think about using a min-heap (or priority queue) to keep track of the smallest current node from each list.

3. Divide and Conquer:

   • Alternatively, you can merge lists in pairs, similar to the merge step in merge sort.

Approach 1: Brute Force

Explanation

• Method:
  • Traverse all linked lists, extract all node values, and store them in an array.
  • Sort the array.
  • Create a new linked list from the sorted array.
• Drawbacks:
  • Requires extra space to store all values.
  • Sorting the array takes O(N log N) time, which may be inefficient if the number of nodes is large.

Pseudocode

values = []
for each list in lists:
    for each node in list:
        values.append(node.val)
sort(values)
dummy = new ListNode()
current = dummy
for value in values:
    current.next = new ListNode(value)
    current = current.next
return dummy.next

Approach 2: Using a Min-Heap (Priority Queue)

Explanation

• Method:
  • Create a min-heap (priority queue) and insert the head of each non-empty linked list.
  • While the heap is not empty:
    • Extract the smallest node from the heap.
    • Append it to the merged list.
    • If the extracted node has a next node, insert that next node into the heap.
• Benefits:
  • Each insertion and extraction from the heap takes O(log k) time, where k is the number of lists.
  • Overall time complexity is O(N log k).

Detailed Walkthrough with Visual Example

Consider the lists:

• List 1: 1 -> 4 -> 5
• List 2: 1 -> 3 -> 4
• List 3: 2 -> 6

Step-by-Step Process:

1. Initialization:
   Insert the head of each list into the heap: Heap = [1 (L1), 1 (L2), 2 (L3)].

2. Iteration:

   • Extract: Pop 1 (from List 1) → Append to result. Insert next node 4 from List 1.
     Heap now: [1 (L2), 2 (L3), 4 (L1)].
   • Extract: Pop 1 (from List 2) → Append to result. Insert next node 3 from List 2.
     Heap now: [2 (L3), 3 (L2), 4 (L1)].
   • Extract: Pop 2 (from List 3) → Append to result. Insert next node 6 from List 3.
     Heap now: [3 (L2), 4 (L1), 6 (L3)].
   • Continue extracting and inserting until the heap is empty.

3. Final Merged List:
   The merged linked list becomes: 1->1->2->3->4->4->5->6.

Pseudocode

initialize a min-heap
for each list in lists:
    if list is not empty:
         push list head into heap
dummy = new ListNode()
current = dummy
while heap is not empty:
    node = heap.pop()
    current.next = node
    current = current.next
    if node.next exists:
         push node.next into heap
return dummy.next

Approach 3: Divide and Conquer

Explanation

• Method:
  • Merge lists in pairs using the two-list merge approach.
  • Recursively merge the resulting lists until one list remains.
• Benefits:
  • This method resembles the merge step of merge sort.
  • Time complexity is O(N log k).

Pseudocode

function mergeKLists(lists):
    if lists is empty:
         return null
    while lists.size > 1:
         mergedLists = []
         for i from 0 to lists.size - 1 in steps of 2:
              list1 = lists[i]
              list2 = lists[i+1] if exists else null
              mergedLists.add(mergeTwoLists(list1, list2))
         lists = mergedLists
    return lists[0]

The helper function mergeTwoLists merges two sorted linked lists.

Code Implementations

Python Code