Merging Sorted Lists, Two Ways

Today's algorithm of the day is the Merge Two Sorted Lists problem:

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

For example, if the first list was 1 > 3 > 5 and the second list was 1 > 4 > 6, the output of the function should be 1 > 1 > 3 > 4 > 5 > 6.

This algorithm is often solved iteratively and recursively, so in this blog post I'll be walking through both solutions. Before I get to the solutions, though, I'll explain what recursion and iteration are, and why they'd be useful in this kind of problem.

Recursion and Iteration: What are They?

"Recursion" and "iteration" are two terms that are often used when describing how to approach an algorithm, and they're often used in comparison.

Iteration means you'll be looping over your code. For example, you'll be writing a while loop or a for loop, and as long as the condition remains true, your function will continue to execute a certain task.

Recursion means you'll be repeatedly calling the function you're currently in. For example, until you get to a base case, your function will continue to call itself and return some value.

You can find more information about these terms here.

I liked this table that spells out the differences (you can find its source here):

Property	Recursion	Interation
Definition	Function calls itself.	A set of instructions repeatedly executed.
Application	For functions.	For loops.
Termination	Through base case, where there will be no function call.	When the termination condition for the iterator ceases to be satisfied.
Usage	Used when code size needs to be small, and time complexity is not an issue.	Used when time complexity needs to be balanced against an expanded code size.
Code Size	Smaller code size	Larger Code Size.
Time Complexity	Very high(generally exponential) time complexity.	Relatively lower time complexity(generally polynomial-logarithmic).

How to Merge Two Lists Iteratively

As discussed above, an iterative approach is one where we'll be looping over some of the code. In the problem of merging lists, we'll want to continue to check the nodes of the list, as long as there are nodes to be checked. I'll first go through the code, and then use an example to illustrate it.

Coding the Iterative Solution

To start this problem, we can create a new list, which we'll be returning at the end of the function. We can do this by creating a new ListNode (a property given to us in the problem), and setting a variable equal to the head of the list.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  //...
}

As long as there are still nodes in both of the inputted lists, we should be comparing their values. Since this is an iterative approach, we'll set up a while loop that keep on executing as long as l1 and l2 are not null.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    //...
  }

  //...
}

An important thing to keep track of while doing iterative solutions is that, at some point, you need to break out of the loop--otherwise, you'll have an infinite loop. That means that inside of the while loop, we have to keep moving forward in both of the inputted lists, so that at some point we get to the end of the list.

Because we're trying to make a sorted list, we'll want to compare the values at the nodes in the list that we're currently on. So, if the value at l1 is less than or equal to the value at l2, we can do something; otherwise, we'll do something else. (Note: it's not necessary for it to be 'less than or equal to'--it would work just as well if we simply said 'less than').

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      //...
    } else {
      //...
    }
  }

  //...
}

In this first case, is the value at l1 is smaller, then we can say that the next node in the list that will be returned will be equal to l1. We can do this by setting current.next equal to l1. We'll also want to keep moving down l1, by setting l1 equal to l1.next. And finally, we'll want to move down the list that will be returned, by setting current equal to current.next.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
      current = current.next;
    } else {
      //...
    }
  }

  //...
}

We can do a similar thing in the 'else' statement. If the value at l2 is smaller, then the next node in the result list will be l2, and we can move down in both l2 and current.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
      current = current.next;
    } else {
      current.next = l2;
      l2 = l2.next;
      current = current.next;
    }
  }

  //...
}

At some point, we'll be getting to the end of one of these lists. If there are still values remaining in l1, but l2 is done being checked, then since l1 is already sorted, we can just add the remainder of l1 to current. Similarly, if there are still values in l2, but l1 is done being checked, we'll add the remainder of l2 to current.

And finally, we can return head.next at the bottom of the function.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
      current = current.next;
    } else {
      current.next = l2;
      l2 = l2.next;
      current = current.next;
    }
  }

  if (l2 === null && l1 !== null) {
    current.next = l1;
  }
  if (l1 === null && l2 !== null) {
    current.next = l2;
  }

  return head.next;
}

Using an Example for the Iterative Solution

Per usual, I like using examples and visuals to explain solutions. For this, I'll use two 2-node lists, where l1 = 1 > 4 and l2 = 2 > 3. When the function starts, we have a new list, as well as the two given lists.

Comparing the first nodes of l1 and 12, 1 <= 2, so 1 (from l1) will go to the new list, and we'll move over to the next node in l1.

Now, we can compare 4 from l1 and 2 from l2. 4 is not <= 2, so we'll go into the else statement. That means we'll add 2 to the result list, and move over to the next node in l2.

No we'll compare 4 from l1 and 3 from l2. 4 is not <= 3, so we'll go into the else statement, and add 3 to the result list. We would move onto the next node in l2, but since there is no next node (it's null), we're done checking l2.

We can't enter the while loop since the conditional statement is no longer true (as l2 is null). Therefore, we can add the remainder of l1 to the result list, and we're done!

How to Merge Two Lists Recursively

Recursively solving this problem would mean repeatedly calling on the function, until we hit some form of a base case. The actual code for the recursive solution is smaller than the iterative solution, but I think it's tricky to wrap your head around a recursive approach. After coding it out in JavaScript, I'll use an example to better explain this approach.

Coding the Recursive Solution

The first thing you'll want to do is set up base cases. Base cases are necessary in recursive solutions because you need to set up a point when the function should stop calling itself.

In this case, we'll want to stop checking the nodes if either l1 or l2 is null. If one of the lists is null, return the other list.

function mergeTwoListsRecursive(l1, l2) {
  if (l1 === null) {
    return l2;
  } else if (l2 === null) {
    return l1;
  }
  //...
}

Now, if the value at l1 is less than the value at l2, we'll move onto the next node in l1 by setting it equal to the function, this time passing in the next node from l1, and the same node from l2. Then, we'll return l1. (I know this is super tricky, but hopefully the explanation later will better explain what's going on here.)

function mergeTwoListsRecursive(l1, l2) {
  if (l1 === null) {
    return l2;
  } else if (l2 === null) {
    return l1;
  }
  if (l1.val < l2.val) {
    l1.next = mergeTwoListsRecursive(l1.next, l2);
    return l1;
  } else {
    //...
  }
}

We'll then do the same if l2 is <= to l1, but this time we'll move to the next node in l2, and recursively call the function by passing in l1 and l2.next. Then, we'll return l2.

function mergeTwoListsRecursive(l1, l2) {
  if (l1 === null) {
    return l2;
  } else if (l2 === null) {
    return l1;
  }
  if (l1.val < l2.val) {
    l1.next = mergeTwoListsRecursive(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoListsRecursive(l1, l2.next);
    return l2;
  }
}

Using an Example for the Recursive Solution

While recursive solutions have some benefits, I find them very hard to understand just by looking at the code alone. If you're like me, walking through an example is very helpful.

I'll use the same example as I did in the iterative solution, so l1 = 1 > 4 and l2 = 2 > 3.

We'll start with the function and both l1 and l2. Since l1.val < l2.val (1 < 2), we'll call the function, this time passing is l1.next (4), and the same l2 (2). We also will return l1, 1, though that's not going to be returned until the very end.

Now, since l1.val is not less than l2.val (4 is not < 2), we'll call the function, this time passing in l2.next (3), and the same l1 (4). We also will return l2, 2.

Again, l1.val is not less than l2.val (4 is not < 3), so we'll call the function, this time passing in the same l1 (4), but null for l2, since there are no more nodes in l2. We'll also return 3.

Since l2 is null, we will return l1, which is 4.

Finally, all of the return statements come together, and we'll return each of these values in order.

--

Please let me know if you have any questions or comments about any of what I've discussed!