Merge Two Lists - Iterative & Recursive Solutions
This is LeetCode problem #21. I liked it so much that I wanted to write a post with an in depth walkthrough of the logic to solve it both iteratively & recursively.
Here’s the problem - you’re given two linked lists that are guaranteed to have values in ascending order. We need to combine these two lists into a single list with values in ascending order. Here’s a visual to help demonstrate what we want to achieve:
As you can see, we can’t just insert one linked list into the other, since we may need to alternate between values from one list and the other several times. This rules out a binary search algorithm 😢. We will need to build a result list by comparing the values from both lists. If you need a refresher on singly linked lists, here is a good resource to read. Basically, we have to access one element at a time, starting at the beginning of the list. Each element has a value and points to the next value (looking at any single element, we have no idea what element came before or if there even was a preceding element - we just know the current element’s value and the next element, if there is one).
The first approach is iterative - we compare the values of the first elements from both lists, appending the smaller value to our result list & then comparing again. By the end we’ll have a sorted linked list. Here’s the code:
Sweet, that will solve the problem. It does seem like a lot of code though, and if you noticed, we’re basically doing the same thing over and over (comparing the first elements of two lists & taking the smaller one). That should have you wondering if we can do the same thing recursively. In this case, using recursion actually reduces the amount of code required by quite a bit! Although recursion often sounds difficult/confusing/scary (believe me, I often feel like that when trying to solve recursive problems), it can be remarkably simple and elegant once you get the hang of it.
In the recursive solution below, we just repeat one step over and over (compare the first node of two lists & take the smaller one). The tricky part is making recursion work. Above all, remember what the function is supposed to do. It returns a sorted list. First we need to handle the base case, which is when we reach the end of either list. If either list has ended, we just return the other (which is a sorted list, so our function does what it’s supposed to in the base case). The next part is to incrementally solve the problem. Since we have two non empty lists, we just need to compare the first node values and select the smaller one. Now that we know the first element in the sorted list, we can recursively call our function to get the rest of the merged list (we need to trust the function to do what it says it does), and then we append the rest of the nodes in sorted order to this first node. We then just return the first/head node in our sorted list & we’re done. Let’s take a look at the code:
It’s so much shorter! I have to admit I needed to think this one through quite a bit to make sense of how it worked. I often have trouble with the “suspension of disbelief” in recursion problems, and I have to work through it step by step (it can be dizzying though). That’s why I emphasized the function doing what it says it does in every code path (base case & recursive case). Then we can trust the function to do what it says it does & each time the function is called recursively it will work towards the base case. It’s quite beautiful once you have it working!
Let’s wrap it up here. Both solutions have the same complexities - time complexity is O(n) since in the worst case (two lists of equal size) we’ll have to iterate through every single element once in order to append it to the result list. Space complexity is also O(1) because we aren’t creating intermediate values - just re-writing list node pointers.
I hope you feel a little more comfortable with recursion after walking through this one (I know I do!). See you next time.