Solution For Merge K Sorted Lists

Problem Statement:
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.

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
] merging them into one sorted list:
1->1->2->3->4->4->5->6

Constraints:
– k == lists.length
– 0 <= k <= 10^4
– 0 <= lists[i].length <= 500
– -10^4 <= lists[i][j] <= 10^4
– lists[i] is sorted in ascending order.
– The sum of lists[i].length won’t exceed 10^4.

Solution:
Approach 1: Brute Force

The brute force solution is quite straightforward. We can store all the nodes of all the linked lists in an array, and then sort the array. Finally, we can construct a new sorted linked list and iterate through the sorted array to add each node into the new list.

The time complexity of this approach is O(NlogN) where N is the total number of nodes in all the k linked lists. Sorting N nodes takes O(NlogN), and iterating N nodes to construct the final linked list takes O(N).

Algorithm:
1. Create a new empty array.
2. Traverse each of the k linked lists, and store all the nodes in the new array.
3. Sort the new array in ascending order.
4. Create a new empty linked list.
5. Traverse the sorted array, and add each node to the new linked list.
6. Return the new linked list.

Code:
“`
class Solution {
public:
ListNode* mergeKLists(vector & lists) {
vector nodes;

    // store all the nodes of all the linked lists in an array
    for (auto& head : lists) {
        for (ListNode* p = head; p != nullptr; p = p->next) {
            nodes.push_back(p->val);
        }
    }

    // sort the array in ascending order
    sort(nodes.begin(), nodes.end());

    // construct a new sorted linked list
    ListNode dummy;
    ListNode* tail = &dummy;
    for (auto val : nodes) {
        tail->next = new ListNode(val);
        tail = tail->next;
    }

    return dummy.next;
}

};
“`

Approach 2: Divide and Conquer

The brute force solution is inefficient because it sorts the nodes in all the linked lists. A more efficient approach is to use a divide-and-conquer technique. We can merge pairs of linked lists repeatedly until there is only one linked list left.

Algorithm:
1. Divide the k linked lists into two halves. (If k is odd, the second half should be larger than the first half.)
2. Recursively merge the two halves into two sorted linked lists.
3. Recursively merge the two sorted linked lists into one sorted linked list.

Code:
“`
class Solution {
public:
ListNode* mergeKLists(vector & lists) {
if (lists.empty()) return nullptr;
int k = lists.size();
while (k > 1) {
int mid = (k + 1) / 2;
for (int i = 0; i < k / 2; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[i + mid]);
}
k = mid;
}
return lists[0];
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy;
    ListNode* tail = &dummy;
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    if (l1 != nullptr) tail->next = l1;
    if (l2 != nullptr) tail->next = l2;
    return dummy.next;
}

};
“`

Step by Step Implementation For Merge K Sorted Lists

/**
 * 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) {
        // check for empty input
        if (lists.length == 0) {
            return null;
        }
        
        // create a min heap
        PriorityQueue 	 	 heap = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
        
        // add the head nodes of all the lists to the heap
        for (ListNode list : lists) {
            if (list != null) {
                heap.add(list);
            }
        }
        
        // create a dummy node to point to the head of the merged list
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        
        // while the heap is not empty
        while (!heap.isEmpty()) {
            // remove the node with the minimum value from the heap
            ListNode minNode = heap.poll();
            
            // add the minimum node to the merged list
            curr.next = minNode;
            curr = curr.next;
            
            // if the minimum node has a next node, add it to the heap
            if (minNode.next != null) {
                heap.add(minNode.next);
            }
        }
        
        // return the head of the merged list
        return dummy.next;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # Base case
        if not lists:
            return None
        
        # Use min heap to track smallest node
        min_heap = []
        for head in lists:
            if head:
                heapq.heappush(min_heap, (head.val, head))
                
        # Extract nodes from min heap and link them
        dummy = ListNode(0)
        curr = dummy
        while min_heap:
            curr.next = heapq.heappop(min_heap)[1]
            curr = curr.next
            if curr.next:
                heapq.heappush(min_heap, (curr.next.val, curr.next))
                
        return dummy.next

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    //edge case
    if (!lists.length) {
        return null;
    }
    
    //helper function to merge two lists
    const merge = (l1, l2) => {
        //base case
        if (!l1) {
            return l2;
        }
        if (!l2) {
            return l1;
        }
        
        //compare l1 and l2 and merge accordingly
        if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        } else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
    
    //helper function to divide lists in half
    const divide = (start, end) => {
        //base case
        if (start === end) {
            return lists[start];
        }
        
        //divide lists in half and merge
        const mid = Math.floor((start + end) / 2);
        const l1 = divide(start, mid);
        const l2 = divide(mid + 1, end);
        return merge(l1, l2);
    }
    
    //call divide to start merging lists
    return divide(0, lists.length - 1);
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector 	 	& lists) {
        // create a min heap
        priority_queue, greater> pq;
        
        // push all the elements of all the linked lists into the min heap
        for(int i = 0; i < lists.size(); i++) {
            ListNode* curr = lists[i];
            while(curr) {
                pq.push(curr->val);
                curr = curr->next;
            }
        }
        
        // create a dummy node
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;
        
        // pop elements from the min heap and add them to the dummy linked list
        while(!pq.empty()) {
            tail->next = new ListNode(pq.top());
            pq.pop();
            tail = tail->next;
        }
        
        return dummy->next;
    }
};

using System; 
using System.Collections.Generic; 
using System.Linq; 

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        // edge case: 
        if (lists.Length == 0) { 
            return null; 
        } 
        
        // create a min heap to store the nodes 
        var heap = new MinHeap(lists.Length); 
        
        // add the head nodes of all the lists to the heap 
        for (int i = 0; i < lists.Length; i++) { 
            if (lists[i] != null) { 
                heap.Add(lists[i]); 
            } 
        } 
        
        // create a new dummy head node 
        ListNode dummy = new ListNode(); 
        ListNode curr = dummy; 
        
        // while the heap is not empty, remove the minimum node 
        // and add it to the merged list 
        while (!heap.IsEmpty()) { 
            curr.next = heap.Remove(); 
            curr = curr.next; 
            
            // if the removed node has a next node, add it to the heap 
            if (curr.next != null) { 
                heap.Add(curr.next); 
            } 
        } 
        
        return dummy.next; 
    }
}

public class MinHeap {
    private List 	 	 _heap;
    
    public MinHeap(int capacity) {
        _heap = new List 	 	(capacity);
    }
    
    public void Add(ListNode node) {
        _heap.Add(node);
        HeapifyUp(_heap.Count - 1);
    }
    
    public ListNode Remove() {
        if (_heap.Count == 0) {
            throw new InvalidOperationException();
        }
        
        ListNode min = _heap[0];
        _heap[0] = _heap[_heap.Count - 1];
        _heap.RemoveAt(_heap.Count - 1);
        HeapifyDown(0);
        
        return min;
    }
    
    public bool IsEmpty() {
        return _heap.Count == 0;
    }
    
    private void HeapifyUp(int index) {
        int parent = (index - 1) / 2;
        
        if (index > 0 && _heap[parent].val > _heap[index].val) {
            Swap(parent, index);
            HeapifyUp(parent);
        }
    }
    
    private void HeapifyDown(int index) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;
        
        if (left < _heap.Count && _heap[left].val < _heap[smallest].val) {
            smallest = left;
        }
        
        if (right < _heap.Count && _heap[right].val < _heap[smallest].val) {
            smallest = right;
        }
        
        if (smallest != index) {
            Swap(smallest, index);
            HeapifyDown(smallest);
        }
    }
    
    private void Swap(int a, int b) {
        ListNode temp = _heap[a];
        _heap[a] = _heap[b];
        _heap[b] = temp;
    }
}