DEV Community

julian
julian

Posted on

Merge Two Sorted Lists Problem

Trying to solve Leetcode problem 21 - Merge 2 sorted lists. Heres the problem below and my own attempt which dosen't work. If anyone can help explain to me the flaw in my logic because it dosen't work :(.

Image description

`var mergeTwoLists = function(list1, list2) {
const final = [];

for (let i=0; i<list1.length; i++) {
    for (let j=0; j<list2.length; j++) {
       if (list2[j] > list1[i]) {
           final.push(list1[i]);
       } else if (list1[i] > list2[j]) {
           final.push(list2[j]);
       } else if (list1[i] == list2[j]) {
           final.push(list1[i], list2[j]);
       }
    }
}
return final;
Enter fullscreen mode Exit fullscreen mode

};`

Top comments (9)

Collapse
 
kamil7x profile image
Kamil Trusiak

This is my idea how to solve this problem: jsfiddle.net/k6uoszvm/

Code:

function merge(listA, listB) {
  // Function must return both lists merged and sorted
  // listA is already sorted, so we can use it as a base
  const newList = [...listA];

  listB.forEach((item) => {
    // For each item in list be we are looking for same 
    // or bigger item in newList and get it's index
    const insertIndex = newList.findIndex(x => x >= item);
    // Now we can add item to newList at found index
    newList.splice(insertIndex, 0, item)
  });

  return newList;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
juliansjy profile image
julian

Thanks for your solution! However, could you explain what the const insertIndex does? I dont understand the "x => x => item" part.

Collapse
 
kamil7x profile image
Kamil Trusiak

It's not x => x => item. It's x => x >= item. I can see source of confusion though. Maybe I should write other way x => item <= x.
If you don't know this syntax, it's arrow function. I could write this with normal function:

newList.findIndex(function(x) {
  return x >= item;
})
Enter fullscreen mode Exit fullscreen mode

Anyway, here is an alogirithm:

For each item in listB, I am looking for first item in newList, that is bigger or equal and then insert item from list B before found.

Example:
List A: 1 2 4
List B: 1 3 4

newList = [...listA] // [1, 2, 4]

Steps while iterating over listB:

  1. First item in list B is 1. First item in new list that is greater or equal is 1, which is at index 0.
  2. Insert 1 into newList at index 0
  3. New list looks like this: [1, 1, 2, 4]
  4. Second item in list B is 3. First item in new list that is greater or equal is 4, which it at index 3.
  5. Insert 3 into newList at index 3
  6. New list looks like this: [1, 1, 2, 3, 4]
  7. Third item in list B is 4. First item in new list that is grater or equal is 4 which is at index 4.
  8. Insert 4 into newList at index 4
  9. New list looks like this: [1, 1, 2, 3, 4, 4]

I hope I explained it better now.

Collapse
 
ashusharmatech profile image
Ashutosh Sharma • Edited

I tried to solve it, here it is onecompiler.com/javascript/3y3uspame

var mergeTwoLists = function(list1, list2) {
const final = [];
let i=0, j=0;
for (; i if (list1[i] > list2[j]) {
final.push(list2[j]);
j++;
} else{
final.push(list1[i]);
i++
}

}

while(i<list1.length ){
final.push(list1[i]);
i++;
}
while(j<list2.length ){
final.push(list2[j]);
j++;
}
return final;
};

Collapse
 
juliansjy profile image
julian

Also, is there a flaw in my logic for the code i first posted? I still don't understand why it is wrong.

Collapse
 
juliansjy profile image
julian

Thanks for the solution! I don't understand line 10 and 11 though. If j is the counter for list2, why is i assigned as the index for list2 in these 2 lines?

Collapse
 
ashusharmatech profile image
Ashutosh Sharma

You are running nested loop which is not useful in this case as the lists are sorted.

The idea here to loop both the list only once.

  1. I have used two couters i and j for itereating both the list respectively.
  2. now counter will only increase if we push from that list.

if the smaller element is in list1 then we will push the element in final list and increase counter i by 1 else push element from list2 and increase counter j by 1.

  1. At the last you need to iterate both the lists to check if there are any remaining element left. if yes push them to final list also.

My suggestion would be try this with putting debugger or some logs in this logic so that you get more understanding.

Collapse
 
himanshu_99 profile image
Himanshu Sahu • Edited

Because the time complexity of above code is very high (i.e. 0(n^2)) that's why it is not accepting and which is also not preferable at interviews and interviewer will ask to optimize the code.
Here is the code you can use as the reference.

class Solution {

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if(list1 == null && list2 == null) return null;

    if(list1 == null) return list2;
    if(list2 == null) return list1;

    if(list1.val < list2.val){
        list1.next = mergeTwoLists(list1.next,list2);
        return list1;
    }else{
        list2.next = mergeTwoLists(list1,list2.next);
        return list2;
    }
}
Enter fullscreen mode Exit fullscreen mode

}