Merge k sorted linked lists and return it as one sorted list in C++

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]

Output: 1->1->2->3->4->4->5->6

This problem can be solved by below given ways:

1. Using Map
2. Using merge Sort or Divide and Conquer
3. Using Recursive
4. Using Priority Queue

Here we shall discuss about 2 solutions

1. Using merge sort or Divide and Conquer
2. Using Recursive

Before looking to the solution, have a look at the previous example where we have merged 2 sorted Linked Lists: < https://www.prodevelopertutorial.com/merge-two-sorted-linked-lists-and-return-it-as-a-new-list-in-c/>

The coding solution given below is self explanatory.

Solution in C++

Output:
List 1 is
1 -> 3 -> 5 -> 7

List 2 is
2 -> 4 -> 6 -> 8

List 3 is
12 -> 14 -> 16 -> 18

The result through recursive is
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 12 -> 14 -> 16 -> 18

/*
* File     : merge_k_sorted_list.cpp
* Author   : ajay.thousand@gmail.com
* Copyright: @ prodevelopertutorial.com
*/

#include<iostream>
#include<vector>

using namespace std;

struct Node 
{
    int data;
    struct Node* next;
};

void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}

 /*Functions for getting result through merge sort START*/   

Node* merge_2_lists(Node* l1, Node* l2)
{
	if(!l1) return l2;
	if(!l2) return l1;

	if(l1->data < l2->data)
	{
		l1->next = merge_2_lists(l1->next, l2);
		return l1;
	}
	else
	{
		l2->next = merge_2_lists(l1, l2->next);
		return l2;
	}
}

Node* partition_merge_sort(vector<Node*>& lists, int start, int end)
{
	if(start == end)
	{
		return lists[start];
	}

	if(start < end)
	{
		int mid = (end+start)/2;

		Node* l1 = partition_merge_sort(lists, start, mid);
		Node* l2 = partition_merge_sort(lists, mid+1, end);
		return merge_2_lists(l1, l2);
	}

	return NULL;
}
    

Node* merge_list_through_merge_sort(vector<Node*>& lists) 
{
   	return partition_merge_sort(lists, 0, lists.size()-1);
}
 
 /*Functions for getting result through merge sort END*/   



 /*Functions for getting result through recursion START*/   

Node* merge_list_through_recursive(vector<Node*>& lists) 
{
    
    if(lists.empty()) return NULL;
    
    while(lists.size() > 1)
    {
        lists.push_back(merge_2_lists(lists[0], lists[1]));
        lists.erase(lists.begin());
        lists.erase(lists.begin());
    }    
    return lists[0];
}
 /*Functions for getting result through recursion END*/   

int main()
{
	vector<Node*> list;

    struct Node *list_1 = NULL; 
    struct Node *list_2 = NULL; 
    struct Node *list_3 = NULL; 
    struct Node *result_list_through_merge_sort = NULL; 


    insert_at_begenning(&list_1,7);
    insert_at_begenning(&list_1,5);
    insert_at_begenning(&list_1,3);
    insert_at_begenning(&list_1,1);


    insert_at_begenning(&list_2,8);
    insert_at_begenning(&list_2,6);
    insert_at_begenning(&list_2,4);
    insert_at_begenning(&list_2,2);

    insert_at_begenning(&list_3,18);
    insert_at_begenning(&list_3,16);
    insert_at_begenning(&list_3,14);
    insert_at_begenning(&list_3,12);

    cout<<"List 1 is\n";
    display_list(&list_1);

    
    cout<<"\nList 2 is\n";
    display_list(&list_2);

    cout<<"\nList 3 is\n";
    display_list(&list_3);

    list.push_back(list_1);
    list.push_back(list_2);
    list.push_back(list_3);

	//result_list_through_merge_sort = merge_list_through_merge_sort(list);
	//cout<<"\nThe result through merge sort is "<<endl;

	result_list_through_merge_sort = merge_list_through_recursive(list);
	cout<<"\nThe result through recursive is "<<endl;

    //result_list_through_merge_sort = merge_list_through_merge_sort(list);
	//cout<<"\nThe result through merge sort is "<<endl;


    display_list(&result_list_through_merge_sort);


    cout<<endl;

}