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!
Top comments (0)