### Merge k Sorted Lists Solution - The Coding Shala

Home >> Interview Prep >> Merge k Sorted Lists

In this post, we will learn how to solve the Merge k Sorted Lists problem and will implement its solution in Java.

## Merge k Sorted Lists Problem

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]
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

## Merge k Sorted Lists Solution

### Approach 1

We can use an additional array to store all the elements from lists and then will sort this array. From the sorted array, we can make the linked list again.

Time Complexity: O(n logn)
Space Complexity: O(N)

Java Program:

```/**
* 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) {
if (lists.length == 0) return null;
if (lists.length == 1) return lists[0];

List<Integer> list = new ArrayList<>();

for (ListNode head : lists) {
}
}

Collections.sort(list);
if(list.size() == 0) return null;
for (int i = 1; i < list.size(); i++) {
ListNode newNode = new ListNode(list.get(i));
temp.next = newNode;
temp = temp.next;
}

}
}```

### Approach 2

Using Recursion and Divide and Conquer approach. We know how to merge two lists and by using a similar approach we will solve this problem.

Read Merge two lists problem Here.

Time Complexity: O(n logn)
Space Complexity: O(1)

Java Program:

```/**
* 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) {
if(lists.length == 0) return null;
return divide(lists, 0, lists.length - 1);
}

// divide here
ListNode divide(ListNode[] lists, int start, int end) {
// base condition
if (start == end) {
return lists[start];
}

int mid = start + (end - start) / 2;
ListNode l1 = divide(lists, start, mid);
ListNode l2 = divide(lists, mid+1, end);

return merge(l1, l2);
}

// merge here
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;
}
}
}
```

Other Posts You May Like