Mergek Sorted Lists Algorithm

The Merge k Sorted Lists algorithm is a technique used in computer science and programming to merge multiple sorted lists into a single, final sorted list. This problem often arises in various applications, such as merging data from multiple sources or combining sorted subarrays during the merge sort algorithm. The primary goal of this algorithm is to efficiently combine the k sorted lists while maintaining the overall sorted order, and it can be achieved through various methods such as divide and conquer, priority queues, or iterative merging. One popular approach to implement the Merge k Sorted Lists algorithm is the divide and conquer method. In this approach, the given k sorted lists are split into pairs, and each pair is merged to produce a new sorted list. This process is repeated until there is only one sorted list remaining. The merging step can be performed using a simple two-pointer technique, where two pointers are initialized at the beginning of each list and advanced through the lists, comparing and selecting the smaller element to be added to the merged list. This process is continued until the end of one of the lists is reached, at which point the remaining elements of the other list are added to the merged list. The time complexity of this algorithm is O(n * log k), where n is the total number of nodes across all lists, and k is the number of sorted lists, making it an efficient solution to the problem.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return merge(lists, 0, lists.size() - 1);
    }
    ListNode* merge(vector<ListNode*>& lists, int left, int right) {
        if (left > right) {
            return NULL;
        }
        if (left == right) {
            return lists[left];
        }
        int mid = (left + right) / 2;
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);
        
        ListNode head(0);
        ListNode* curr = &head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                curr->next = l1;
                l1 = l1->next;
            } else {
                curr->next = l2;
                l2 = l2->next;
            }
            curr = curr->next;
        }
        while (l1) {
            curr->next = l1;
            l1 = l1->next;
            curr = curr->next;
        }
        while (l2) {
            curr->next = l2;
            l2 = l2->next;
            curr = curr->next;
        }
        return head.next;
    }
};

LANGUAGE:

DARK MODE: