I don't understand this LeetCode problem solution

Question

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists. The examples below.

Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]

Input: l1 = [], l2 = [] Output: []

Input: l1 = [], l2 = [0] Output: [0]

This is the solution I have:

var mergeTwoLists = function(l1, l2) {
  if(!l1 || !l2) return (l1? l1:l2);
  if(l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

Can someone please explain this solution line by line? Thank you so much!

Is there part(s) you do understand? Is there something we should focus on? — VLAZ
– VLAZ, Commented Jul 13, 2021 at 9:10

jkoestinger · Accepted Answer · 2021-07-13 09:21:17Z

It's a recursive method. So first you need a base case to make sure it will be able to stop at some point.

Here, it's the first condition (if one of the args is missing, just return the other one). Note that this works even if the function was called initially with one empty list, so this seems relevant.

Then basically it checks which list has the lowest first element (this is the correct idea: the lowest value out of the two is the one that should go to the result first).

After this, the element you just retained will be prepended with the result of the same function minus the item you just selected (since it is now the first element).

So here is an example

1 -> 5 -> 10
3 -> 4 -> 9 -> 11

The idea is then to say "The result should start by either 1 or 3, and then the rest of the sorted list". So you choose the lowest one:

Result: 1

5 -> 10
3 -> 4 -> 9 -> 11

Then you can repeat the process by just calling the function on the remaining lists and append the new value to your result (so here you have to choose between 5 and 3):

Result: 1 -> 3

5 -> 10
4 -> 9 -> 11

and you repeat until you only get one list left:

Result: 1 -> 3 -> 4 -> 5 -> 9 -> 10

11

And here you could just append the last list completely (here there is only one element, but it would work even if there were more).

I hope I've been clear enough :)

ikhvjs · Accepted Answer · 2021-07-13 09:23:16Z

First, the l1 and l2 are passed as a link list object. They are not an array.

if (!l1 || !l2) return l1 ? l1 : l2; return one list if one of them is null.

l1.next = mergeTwoLists(l1.next, l2) It is a recursive call and it assigns the next point to a merged List from two other lists l1.next and l2.

l2.next = mergeTwoLists(l1, l2.next)is also the same logic.

As a result, the final result will be a merged list of all the merged list of next nodes.

var mergeTwoLists = function (l1, l2) {  
  if (!l1 || !l2) return l1 ? l1 : l2; //return one list if one of them is null
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2); //return the merged List from the two input list
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next); //return the merged List from the two input list
    return l2;
  }
};

Collectives™ on Stack Overflow

I don't understand this LeetCode problem solution

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related