# Solution For Merge K Sorted Lists

Problem Statement:
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

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

Constraints:
– k == lists.length
– 0 <= k <= 10^4
– 0 <= lists[i].length <= 500
– -10^4 <= lists[i][j] <= 10^4
– lists[i] is sorted in ascending order.
– The sum of lists[i].length won’t exceed 10^4.

Solution:
Approach 1: Brute Force

The brute force solution is quite straightforward. We can store all the nodes of all the linked lists in an array, and then sort the array. Finally, we can construct a new sorted linked list and iterate through the sorted array to add each node into the new list.

The time complexity of this approach is O(NlogN) where N is the total number of nodes in all the k linked lists. Sorting N nodes takes O(NlogN), and iterating N nodes to construct the final linked list takes O(N).

Algorithm:
1. Create a new empty array.
2. Traverse each of the k linked lists, and store all the nodes in the new array.
3. Sort the new array in ascending order.
4. Create a new empty linked list.
5. Traverse the sorted array, and add each node to the new linked list.
6. Return the new linked list.

Code:
“`
class Solution {
public:
ListNode* mergeKLists(vector & lists) {
vector nodes;

``````    // store all the nodes of all the linked lists in an array
for (auto& head : lists) {
for (ListNode* p = head; p != nullptr; p = p->next) {
nodes.push_back(p->val);
}
}

// sort the array in ascending order
sort(nodes.begin(), nodes.end());

// construct a new sorted linked list
ListNode dummy;
ListNode* tail = &dummy;
for (auto val : nodes) {
tail->next = new ListNode(val);
tail = tail->next;
}

return dummy.next;
}
``````

};
“`

Approach 2: Divide and Conquer

The brute force solution is inefficient because it sorts the nodes in all the linked lists. A more efficient approach is to use a divide-and-conquer technique. We can merge pairs of linked lists repeatedly until there is only one linked list left.

Algorithm:
1. Divide the k linked lists into two halves. (If k is odd, the second half should be larger than the first half.)
2. Recursively merge the two halves into two sorted linked lists.
3. Recursively merge the two sorted linked lists into one sorted linked list.

Code:
“`
class Solution {
public:
ListNode* mergeKLists(vector & lists) {
if (lists.empty()) return nullptr;
int k = lists.size();
while (k > 1) {
int mid = (k + 1) / 2;
for (int i = 0; i < k / 2; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[i + mid]);
}
k = mid;
}
return lists[0];
}

``````ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* tail = &dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if (l1 != nullptr) tail->next = l1;
if (l2 != nullptr) tail->next = l2;
return dummy.next;
}
``````

};
“`

## Step by Step Implementation For Merge K Sorted Lists

```/**
* 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) {
// check for empty input
if (lists.length == 0) {
return null;
}

// create a min heap
PriorityQueue 	 	 heap = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);

// add the head nodes of all the lists to the heap
for (ListNode list : lists) {
if (list != null) {
}
}

// create a dummy node to point to the head of the merged list
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;

// while the heap is not empty
while (!heap.isEmpty()) {
// remove the node with the minimum value from the heap
ListNode minNode = heap.poll();

// add the minimum node to the merged list
curr.next = minNode;
curr = curr.next;

// if the minimum node has a next node, add it to the heap
if (minNode.next != null) {
}
}

// return the head of the merged list
return dummy.next;
}
}```
```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# Base case
if not lists:
return None

# Use min heap to track smallest node
min_heap = []

# Extract nodes from min heap and link them
dummy = ListNode(0)
curr = dummy
while min_heap:
curr.next = heapq.heappop(min_heap)[1]
curr = curr.next
if curr.next:
heapq.heappush(min_heap, (curr.next.val, curr.next))

return dummy.next```
```/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
//edge case
if (!lists.length) {
return null;
}

//helper function to merge two lists
const merge = (l1, l2) => {
//base case
if (!l1) {
return l2;
}
if (!l2) {
return l1;
}

//compare l1 and l2 and merge accordingly
if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
} else {
l2.next = merge(l1, l2.next);
return l2;
}
}

//helper function to divide lists in half
const divide = (start, end) => {
//base case
if (start === end) {
return lists[start];
}

//divide lists in half and merge
const mid = Math.floor((start + end) / 2);
const l1 = divide(start, mid);
const l2 = divide(mid + 1, end);
return merge(l1, l2);
}

//call divide to start merging lists
return divide(0, lists.length - 1);
};```
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector 	 	& lists) {
// create a min heap
priority_queue, greater> pq;

// push all the elements of all the linked lists into the min heap
for(int i = 0; i < lists.size(); i++) {
ListNode* curr = lists[i];
while(curr) {
pq.push(curr->val);
curr = curr->next;
}
}

// create a dummy node
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;

// pop elements from the min heap and add them to the dummy linked list
while(!pq.empty()) {
tail->next = new ListNode(pq.top());
pq.pop();
tail = tail->next;
}

return dummy->next;
}
};```
```using System;
using System.Collections.Generic;
using System.Linq;

public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}

public class Solution {
public ListNode MergeKLists(ListNode[] lists) {
// edge case:
if (lists.Length == 0) {
return null;
}

// create a min heap to store the nodes
var heap = new MinHeap(lists.Length);

// add the head nodes of all the lists to the heap
for (int i = 0; i < lists.Length; i++) {
if (lists[i] != null) {
}
}

// create a new dummy head node
ListNode dummy = new ListNode();
ListNode curr = dummy;

// while the heap is not empty, remove the minimum node
// and add it to the merged list
while (!heap.IsEmpty()) {
curr.next = heap.Remove();
curr = curr.next;

// if the removed node has a next node, add it to the heap
if (curr.next != null) {
}
}

return dummy.next;
}
}

public class MinHeap {
private List 	 	 _heap;

public MinHeap(int capacity) {
_heap = new List 	 	(capacity);
}

HeapifyUp(_heap.Count - 1);
}

public ListNode Remove() {
if (_heap.Count == 0) {
throw new InvalidOperationException();
}

ListNode min = _heap[0];
_heap[0] = _heap[_heap.Count - 1];
_heap.RemoveAt(_heap.Count - 1);
HeapifyDown(0);

return min;
}

public bool IsEmpty() {
return _heap.Count == 0;
}

private void HeapifyUp(int index) {
int parent = (index - 1) / 2;

if (index > 0 && _heap[parent].val > _heap[index].val) {
Swap(parent, index);
HeapifyUp(parent);
}
}

private void HeapifyDown(int index) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int smallest = index;

if (left < _heap.Count && _heap[left].val < _heap[smallest].val) {
smallest = left;
}

if (right < _heap.Count && _heap[right].val < _heap[smallest].val) {
smallest = right;
}

if (smallest != index) {
Swap(smallest, index);
HeapifyDown(smallest);
}
}

private void Swap(int a, int b) {
ListNode temp = _heap[a];
_heap[a] = _heap[b];
_heap[b] = temp;
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]