LeetCode #21: Merge Two Sorted Lists

Up till now, we haven't done any problems involving linked lists, but I feel like this is a great problem to get started. The merge two sorted lists problem is quite straightforward - you're given two sorted linked lists, and all you have to do is merge the two together into one sorted list and return it.

This is the example given to us and it's pretty self-explanatory. We need to traverse the nodes of both lists and merge them in ascending order. As mentioned in the constraints of the question, both lists provided to us are in ascending order, so we don't need to worry about sorting the individual lists.

There are two more examples provided and it's important that you carefully analyze them. In most cases, when it comes to solving problems in LeetCode, there's hidden information that you can extract from the example test cases. For instance, looking at example 3, we can infer that if list 1 is null, then we only need to return list 2:

And this makes for a great base case. So, to start solving the problem, we can just take care of cases where either list 1 or list 2 doesn't exist. In code, that means:

 if (!l1) {
    return l2;
  }
  if (!l2) {
    return l1;
  }

With that out of the way, we can start working on our merged list, and for that, we first need something to hold our merged list:

let mergedNode;

Now, let's start traversing our lists. If the value of the node of the first list is less than the value of the node of the second list, that means we need to make a new node in the merged list that stores the smaller value. For instance, if we have two lists, [1,2,3] and [4,5,6], then the value of the first node in our merged list should be 1. If we translate that into code, we get:

if (l1.val < l2.val) {
    mergedNode = new ListNode(l1.val);

If you're familiar with linked lists, you know that you need to define what the next node for our merged list should be. In this case, the next node will be either the next node in our first list or the first node in our second list, depending on which one's smaller. In our example, the next node can be either 2 from the first list or 4 from the second list. And this is where recursion is a great choice - we have to check the smaller value from the two lists repeatedly.

But what arguments are you going to pass to the function?

Well, that's easy. We've already used the current value of l1 for our merged node. That means the next value we need to check is l1.next while the second argument is going to be l2 since we haven't used any node from the second list. That means our recursive call would be:

mergedNode.next = mergeTwoLists(l1.next, l2);

If this sounds confusing, let's understand this with a rough drawing of our example. Here are our two lists and since 1 is less than 4, that's going to be the first node for our sorted merged list:

After 1, the next node in our merged list can either be 2 (which is l1.next) or 4 (which is l2):

Of course, since our merged list must be sorted in ascending order, the next node is going to be 2. So put together, this is what the if condition looks like:

 if (l1.val < l2.val) {
    mergedNode = new ListNode(l1.val);
    mergedNode.next = mergeTwoLists(l1.next, l2);
  }

But what if l2.val is bigger? We'll take care of that in our else, and we'll basically use the same logic we used above. The only difference is that we'll need to pass l2.next and l1 to our recursive function. Here's what I mean:

else {
    mergedNode = new ListNode(l2.val);
    mergedNode.next = mergeTwoLists(l2.next, l1);
  }

Once all the nodes are traversed, all that's left to do is return the merged list:

  return mergedNode;

And that's all you need to do to solve this problem. Of course, you can also solve this problem iteratively, but the recursive approach is easier to understand and implement. The runtime for this solution is O(n+m) where n is the number of nodes in l1 and m is the number of nodes in l2. As always, you can find the complete code on my GitHub!

Solving Leetcode problems is hard enough as it is, and add to that the difficulty of finding an in-depth solution that explains everything, and you find yourself stuck. Some videos are hard to follow, some don't explain the basics, while others leave you with more questions than answers. In this series, I break down Leetcode problems one at a time and walk you through a step-by-step solution. Have a question you can't understand? Send it to me, and I'll explain it in detail. And don't forget to subscribe to my newsletter to get my articles directly into your inbox!