How to Solve Merge Two Sorted Lists in an Interview

This problem is written as a linked list problem to challenge your understanding of objects and references. Here are some tricks for working with linked lists:

If a problem requires creating and returning a new list, you should always start it with a “dummy” ListNode. This dummy node’s value can be anything. The dummy node’s next pointer will point to the actual start of the list. When you’re ready to return the list, return the dummy’s next. We don’t want to include the value of the dummy node in our return.

We want to use a dummy ListNode because it will clean up your code. For this problem, it saves you from writing edge case code and follows the “Don’t Repeat Yourself” (DRY) best practice. Here is what the code would look like if you initialized your first ListNode to the actual value instead of a dummy:

We don’t know when a Linked List ends. We can’t reference its size given a node in the list. Therefore, we must always use a while loop to iterate through the nodes.

To do this (without losing the pointer to the head of the list), we need to create a new ListNode that points to the list. This pointer is usually named curr. In the while loop, we will move curr forward to the next node in the list. Thus, the condition for the while loop is curr != null.

Like Two Sum, this is a Two Pointers problem. This is because we have to evaluate both lists at once to find the lower value. Tell your interviewer that you will approach this with two pointers.

Let’s show an interviewer how we would begin solving the problem.

I’ve demonstrated many iterations to help illustrate what the algorithm is doing. This is a brute force solution, but with a twist: the second pointer is always ahead of the first, making the actual code of the algorithm slightly different than a classic brute force approach. Before you begin coding, it may also be helpful to ask how to handle edge cases - like how to handle there being no solution for the input. Now that we have the concept in our heads, let’s code.

I find it helpful to translate your concept to pseudocode comments. This will demonstrate what you want your code to do. This will also make it easier for your interviewer to follow your thinking. Depending on your interviewer, they may even stop your solution here.

Now, you can convert your pseudocode to real code.

Now that you have completed your code, your interviewer will ask you the time and space complexity.

Here, you would think about the worst case scenario. Since we have to see every node to know which one goes next in the result list, the time complexity is O(N + M). The space complexity is O(1) because we created one dummy node.

You may be wondering, if we are returning a new list, how is space complexity only O(1)? This is because all of the nodes in the new list already exist, We are only changing the pointers of each node.

Next, your interviewer will ask you if there is any way to optimize the code.

When one of the lists has been fully merged into list3, we still need to merge the rest of the second list. In our current implementation, we continue to iterate through the remainder of the second list. Given your understanding of Linked Lists, does this seem necessary? Let’s think about what we are doing: we are assigning the next field of each ListNode. What are we assigning it to? The next ListNode, which it is already pointing to.

Therefore, we can simply point to the start of the remainder of the list. The nodes in the remainder of the list are already pointing to the correct nodes. This will improve our runtime complexity!