Merge k Sorted Arrays

Problem Statement: You are given an array of k linked-lists lists, each linked list is sorted in ascending order. You need to merge all the linked list into a single linked list and return it.

Example:

Example 1:
Input: [[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
] 
 
Merged Linked list will be
1  ⇾ 1 ⇾ 2  ⇾ 3  ⇾ 4  ⇾ 4  ⇾ 5  ⇾ 6

Example 2: 
Input: [[1, 2, 3], [4, 5, 6], [7 ,8, 9]]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Explanation: The linked-lists are:
[
1 ⇾ 2  ⇾ 3,
4  ⇾ 5  ⇾ 6,
7  ⇾ 8  ⇾ 9
]
Merged Linked list will be
1  ⇾ 2  ⇾ 3  ⇾ 4  ⇾ 5  ⇾ 6  ⇾ 7  ⇾ 8  ⇾ 9

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution: 1

Approach:  The first approach that comes to mind is to traverse all linked lists one by one and merge them while traversing. In simple words start from the first list in the array and start merging it with the rest of the lists in the array.

For this initialize a dummy node, don’t worry about algorithms questions, we always pass the head of the linked list as the argument. If we are changing the position of the head node, and you need to return the new head node, the problem will be how you are going to return the new head. That’s why we initially create a dummy node and dummy. Next will point to the head. So, if you are potentially modifying the head of the list, use a dummy node.

So,

Step 1: Initialise a dummy node 

Linked List dummy_node = new Linked List();

Step 2: Start traversing the linked list, merge it in a sorted fashion, and connect the head of the newly created linked list to the next of the dummy node. 

Here we assume that you know how to merge two sorted linked list

Code:

C++ Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* list1, ListNode* list2) {

        // initialising result node
        ListNode* res = new ListNode(0);
        ListNode* tail = res;

        // if you had solved previous merge two sorted linked list
        // then this is easy to understand

        // here loop will execute until any of the list is not empty
        while (list1 != NULL && list2 != NULL) {

            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            // tail has to be incremented after every iteration
            // that's why it is kept outside of the if else statement
            tail = tail->next;
        }

        // if any of list becomes empty then append that list to the tail of the resultant list

        if (list1 == NULL)
            tail->next = list2;
        else
            tail->next = list1;

        return res->next;
    }

    ListNode* mergeKLists(vector<ListNode*> &lists) {

        // initialising result node

        // creating the dummy node is the common technique
        // to avoid any edge cases
        ListNode* res = new ListNode(0);

        for (ListNode* list: lists) {
            res->next = merge(res->next, list);
        }

        return res->next;
    }

 
};

Output:

Time Complexity:  O(K*N) where “K” is the number of linked lists in the array and “N” is the number of nodes

Space Complexity: O(1) Since we are not using any extra space.

Java Code

/**
 * 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 List Node mergeKLists(ListNode[] lists) {

        // initialising result node

        // creating the dummy node is the common technique
        // to avoid any edge cases
        ListNode res = new ListNode(0);

        for (ListNode list: lists) {
            res.next = merge(res.next, list);
        }

        return res.next;
    }

    public ListNode merge(ListNode list1, ListNode list2) {

        // initialising result node
        ListNode res = new ListNode(0);
        ListNode tail = res;

        // if you had solved previous merge two sorted linked list
        // then this is easy to understand

        // here loop will execute until any of the list is not empty
        while (list1 != null && list2 != null) {

            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            // tail has to be incremented after every iteration
            // that's why it is kept outside of the if else statement
            tail = tail.next;
        }

       // if any of list becomes empty then append that list to the tail of the 
       //resultant list

        if (list1 == null)
            tail.next = list2;
        else
            tail.next = list1;

        return res.next;
    }
}

Time Complexity:  O(K*N) where “K” is the number of linked lists in the array and “N” is the number of nodes

Space Complexity: O(1) Since we are not using any extra space.

Solution: 2

Approach: This is a “Divide and Conquer” technique. If you don’t know about this technique then no need to worry it is just an algorithmic paradigm that we use to divide a large problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

In this approach, we will initially divide the linked list until it becomes impossible to further divide that into individual nodes.

Then we start merging nodes in a sorted manner at the last we will get the merged sorted linked list.

Code:

C++ Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(vector<ListNode*> lists, int start, int end) {
        if (start == end) 
            return lists[start];
        
        if (start < end) {
            
            int mid = start + (end - start) / 2;
            
            ListNode* l1 = partition(lists, start, mid);
            ListNode* l2 = partition(lists, mid + 1, end);
            
            return merge(l1, l2);
        } 
        else
            return NULL;
    }
 
    //This function is from Merge Two Sorted Lists.
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if (l1 == NULL)
            return l2;
        
        if (l2 == NULL)
            return l1;
        
        if (l1->val < l2->val) {
            l1->next = merge(l1->next, l2);
            return l1;
        } 
        else {
            l2->next = merge(l1, l2->next);
            return l2;
        }
    }

    ListNode* mergeKLists(vector<ListNode*> &lists) {

       return partition(lists, 0, lists.size() - 1);
    }
 
};

Time Complexity:  O(N*logK) where “logK” is because we are dividing the linked list into 2 i.e k/2, k/4 in each level of recursion so in total we are doing it logK times, “N” is the total number of nodes

Space Complexity: O(1) Since we are not using any extra space.

Java Code

/**
 * 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) {
        
        return partition(lists, 0, lists.length - 1);
        
    }
 
    // this function will partition linked list
    public ListNode partition(ListNode[] lists, int start, int end) {
        if (start == end) 
            return lists[start];
        
        if (start < end) {
            
            int mid = start + (end - start) / 2;
            
            ListNode l1 = partition(lists, start, mid);
            ListNode l2 = partition(lists, mid + 1, end);
            
            return merge(l1, l2);
        } 
        else
            return null;
    }
 
    //This function is from Merge Two Sorted Lists.
    public ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        
        if (l2 == null)
            return l1;
        
        if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        } 
        else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}

Time Complexity:  O(N*logK) where “logK” is because we are dividing the linked list into 2 i.e k/2, k/4 in each level of recursion so in total we are doing it logK times, “N” is the total number of nodes

Space Complexity: O(1) Since we are not using any extra space.

Special thanks to Ishu Prabhakar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article