How to merge K sorted linked list and return a sorted linked list in the end

Gursimrat saini — Fri, 26 Apr 2024 22:49:42 +0000

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

The array is empty i.e Array: []

Second Edge Case

The array has an empty linked list i.e Array:[[]]

Handle first edge case


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

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

Array.prototype.sort()

Here is the link to the mdn to check the documentation of this method Sort Method of Array

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

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...

   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

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

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

Happy Coding!

DEV Community: Gursimrat saini

How to merge K sorted linked list and return a sorted linked list in the end

First Edge Case

Second Edge Case