Home Â» Technical Interview Questions Â» LinkedList Interview Questions Â» Merge K Sorted Linked Lists

# Merge K Sorted Linked Lists

Merge K sorted linked lists problem is so famous as per the interview point of view. This question asks so many times in big companies like Google, Microsoft, Amazon, etc.Â  As the name suggests we’ve been provided with k sorted linked lists. We have to merge them together into a Single Sorted Linked List.

Let’s look into a sample test case to understand it better:

## Example

[

1->2->3,

1->4->6,

2->3

]

### Output

1->1->2->2->3->3->4->6

## Approach-1 for Merge K Sorted Linked Lists

### Brute ForceÂ

• Traverse all the linked lists and put all the values in an Array/ArrayList/Vector(Whatever storage you find convenient)
• Sort the data
• Create a new linked list from the sorted data

Let’s understand that better by a code

### Java Program

```class Solution
{
public ListNode mergeKLists(ListNode[] lists)
{
ListNode aux=new ListNode(0);
List<Integer>lisa=new ArrayList<Integer>();
for(int i=0;i<lists.length;i++)
{
ListNode ptr=lists[i];
while(ptr!=null)
{
ptr=ptr.next;
}
}
Collections.sort(lisa);
ListNode ptr=aux;
for(int i=0;i<lisa.size();i++)
{
ListNode temp=new ListNode(lisa.get(i));
temp.next=null;
ptr.next=temp;
ptr=ptr.next;
}
return aux.next;
}
}```

### C++ Program

```class Solution
{
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
vector<int>store;
for(int i=0;i<lists.size();i++)
{
ListNode *ptr=lists[i];
while(ptr!=NULL)
{
store.push_back(ptr->val);
ptr=ptr->next;
}
}
sort(store.begin(),store.end());
ListNode *ptr=new ListNode();
ListNode *aux=ptr;
for(int i=0;i<store.size();i++)
{
ListNode *temp=new ListNode(store[i]);
temp->next=NULL;
ptr->next=temp;
ptr=ptr->next;
}
return aux->next;
}
};```
```[

1->2->3,

1->4->6,

2->3

]```
`1->1->2->2->3->3->4->6`

### Complexity Analysis

Let us now look into the time complexity of the above solution:

The time is taken for traversal and creation: O(n)

READ  Delete Nth node from the end of the given linked list

The time is taken for sorting: O(n log n)

Making the time complexity: O(n log n)

## Approach-2 for Merge K Sorted Linked Lists

### Using Min-Heap

A Priority Queue can be used as a storage

• No need for sorting

Let’s look into the same with the help of a code

### Java Program

```class Solution
{
public ListNode mergeKLists(ListNode[] lists)
{
Queue<Integer>store=new PriorityQueue();
for(int i=0;i<lists.length;i++)
{
ListNode ptr=lists[i];
while(ptr!=null)
{
ptr=ptr.next;
}
}
if(store.isEmpty() )
return null;
while(!store.isEmpty())
{
ListNode temp=new ListNode(store.poll());
cur.next=temp;
cur=cur.next;
}
}
}```
```[
2->5->7->9,
1->2->3->->10
]```
`1->2->2->3->5->7->9->10`

### Complexity Analysis

The time complexity of the above: O(n log n)

## Approach-3 for Merge K Sorted Linked Lists

### Divide and Conquer

• The Divide step

OBJECTIVE-Sends k lists to merge function k/2 at time

• The Merge step

OBJECTIVE-To consider smaller values and add them to create a new list

• Create a pointer to return the combined list
• Add the smaller value from either list
• Increment pointer from which value has been taken
• Return merged and sorted linked list from two lists

Let’s understand that better with the help of code

### Java Program

```class Solution
{
public static ListNode merge(ListNode l1,ListNode l2)
{
if(l1==null)
return l2;
if(l2==null)
return l1;
ListNode aux=new ListNode();
while(l1!=null && l2!=null)
{
if(l1.val>l2.val)
{
aux.next=l2;
l2=l2.next;
}
else
{
aux.next=l1;
l1=l1.next;
}
aux=aux.next;
}
if(l1!=null)
aux.next=l1;
else if(l2!=null)
aux.next=l2;
}
public static ListNode divide(ListNode[]lists,int start,int end)
{
if(end<start)
return null;
if(end==start)
return lists[start];
int mid=start+(end-start)/2;
return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
}
public ListNode mergeKLists(ListNode[] lists)
{
if(lists == null)
return null;
if(lists.length == 1)
return lists[0];
return divide(lists,0,lists.length-1);
}
}```

### C++ Program

```class Solution
{
public:
ListNode* merge(ListNode *l1,ListNode *l2)
{
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
ListNode *aux=new ListNode();
while(l1!=NULL && l2!=NULL)
{
if(l1->val>l2->val)
{
aux->next=l2;
l2=l2->next;
}
else
{
aux->next=l1;
l1=l1->next;
}
aux=aux->next;
}
if(l1!=NULL)
aux->next=l1;
else if(l2!=NULL)
aux->next=l2;
}
public:
ListNode* divide(vector<ListNode*>&lists,int start,int end)
{
if(end<start)
return NULL;
if(end==start)
return lists[start];
int mid=start+(end-start)/2;
return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
if(lists.size() == 0)
return NULL;
if(lists.size() == 1)
return lists[0];
return divide(lists,0,lists.size()-1);
}
};```
```[
1->2,
3,
4->5->6->7,
8->9->10,
11
]```
`1->2->3->4->5->6->7->8->9->10->11`

### Complexity Analysis

The time complexity=O(n log n)

The space complexity=O(1)

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions