How to merge K sorted linked list and return a sorted linked list in the end
Published: 2024-04-26 22:49:42

Suppose you are given an array of K sorted linked lists and the challenge here is to merge those sorted linked lists and return a sorted linked list.

For example: [[1,4,5],[1,8,9],[6,8,7]].
The result: [1,1,4,5,6,7,8,8,9].

Now what to do?
Before checking out the solution, what solutions will come to your mind?

There are many ways to solve this problem, but shouldn't we discuss the edge cases too?

### First Edge Case
1. The array is empty i.e Array: []

### Second Edge Case
2. The array has an empty linked list i.e Array:[[]]

**Handle first edge case**

```javascript

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if(!lists || lists.length===0){
        return null;
    }
}
```
To approach the problem I have added all the values of the nodes to the array by mapping the lists array 

``` javascript
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if(!lists || lists.length===0) {
        return null;
    }

   let listNodeArray=[];
   lists.map((eachNode:ListNode) => { 
     // handle second edge case
     if(eachNode==null) return null;
 
     let tempNode=eachNode;
     while(tempNode.next!==null) {
       nodeArr.push(tempNode.val);
       tempNode=tempNode.next;
     }
    nodeArr.push(tempNode.val);
 })
}

```
After getting all the node values in the array we need to sort them using
```javascript 
Array.prototype.sort()
``` 
Here is the link to the mdn to check the documentation of this method [Sort Method of Array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort)

Here is the code to sort the array values in ascending order 

```javascript 
const newSortedArr=nodeArr.sort((a,b)=> a-b);
``` 
 Now I have the sorted Array, I need to convert the array to a linked list. I think it's pretty easy.

Here is the code to do it...

```javascript 
   let head=new ListNode(-1)
   let newNode=head;
    for(let i=0;i<newSortedArr.length;i++){
      newNode.next=new ListNode(newSortedArr[i]);
      newNode=newNode.next
    }
``` 

Now we just need to return head.next


```javascript 
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if(!lists || lists.length===0) {
        return null;
    }

   let listNodeArray=[];
   lists.map((eachNode:ListNode) => { 
     // handle second edge case
     if(eachNode==null) return null;
    
    // Create a tempNode and assign eachNode to it 
   // so that we can iterate through each node in the list
  
     let tempNode=eachNode;
     while(tempNode.next!==null) {
       nodeArr.push(tempNode.val);
       tempNode=tempNode.next;
     }
    nodeArr.push(tempNode.val);
 })

   const newSortedArr=nodeArr.sort((a,b)=> a-b);

   let head=new ListNode(-1);
   let newNode=head;

   for(let i=0;i<newSortedArr.length;i++) {
      newNode.next=new ListNode(newSortedArr[i]);
      newNode=newNode.next
    }

  return head.next;

}
```

This solution beats the runtime 

![Runtime image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ue6lwkl0998b8mrzxzx3.png)

You can find this problem at leetCode and try by yourself before coming to visit this solution. 

Happy Coding!