Merge Two Sorted Lists LeetCode — Complete Walkthrough

Merge Two Sorted Lists (#21) is the first linked list problem most people tackle on LeetCode, and for good reason. It introduces two ideas you will use for the rest of your coding interview career: the dummy node technique and the merge step from merge sort.

If you have ever studied merge sort, you already know half the answer. The "merge" in merge sort is exactly this problem — take two sorted sequences and combine them into one sorted sequence. LeetCode #21 simply asks you to do it with linked lists instead of arrays.

In this walkthrough, we will break down both the iterative and recursive approaches to merge two sorted lists on LeetCode, explain why the dummy node exists, cover every edge case, and show you where this pattern appears in harder problems.

You are given the heads of two sorted linked lists, list1 and list2. Your job is to merge them into one sorted list by splicing the existing nodes together. Return the head of the merged linked list.

For example, if list1 is 1 -> 2 -> 4 and list2 is 1 -> 3 -> 4, the output should be 1 -> 1 -> 2 -> 3 -> 4 -> 4. The key constraint is that you must reuse the existing nodes — you are not creating new ones.

This is classified as an Easy problem, but do not let that fool you. The technique you learn here is the exact merge step used in Merge K Sorted Lists (#23), which is a Hard. Master it once, and the harder variants become approachable.

The iterative solution is the one you should reach for in an interview. It uses O(n+m) time and O(1) extra space — no recursion stack, no auxiliary data structures. The idea is straightforward: maintain a pointer that builds the result list one node at a time.

Start by creating a dummy node. This dummy serves as a placeholder head so you never have to worry about which list provides the first element. Then use a current pointer that starts at dummy and walks forward as you attach nodes.

At each step, compare the values at the heads of list1 and list2. Whichever is smaller, attach it to current.next and advance that list pointer. Then advance current. When one list is exhausted, attach the remainder of the other list directly — it is already sorted.

The recursive approach is elegant and often easier to write from scratch. The idea is simple: compare the two heads, pick the smaller one, and recursively merge the rest. The base case is when one list is null — return the other.

If list1.val is less than or equal to list2.val, then list1 should be the current node in the result. Set list1.next to the result of merging list1.next with list2, then return list1. The mirror case handles when list2 is smaller.

The recursive solution has the same O(n+m) time complexity as the iterative approach, but it uses O(n+m) stack space due to the recursive calls. For short lists this is fine, but for lists with tens of thousands of nodes, the iterative approach is safer.

The dummy node is arguably the most important takeaway from this problem. Without it, you would need special-case logic to determine which list provides the first node of the result. With the dummy node, you skip that entirely.

Here is why it matters: if you try to build the result without a dummy, you have to write an if-else block before the loop to initialize the head. This is error-prone and clutters the code. The dummy node eliminates that branch completely — you always attach to current.next, and at the end you return dummy.next.

You will see the dummy node technique reappear in problems like Partition List (#86), Add Two Numbers (#2), and any problem where you are constructing a new linked list from scratch. Learn it here, and it becomes second nature.

Edge cases are where interview candidates lose points, and merge two sorted lists has several worth knowing. Always think about what happens when the inputs are unusual.

The most common edge case is when one or both lists are empty. If list1 is null, return list2 immediately. If list2 is null, return list1. The dummy node approach handles this naturally since the while loop simply never executes.

Other cases to consider: all elements come from one list (the other is always larger), both lists have a single element, and the lists are already interleaved perfectly. Test your solution mentally against each of these before submitting.

This problem is not just an Easy to check off your list. It teaches two patterns that show up constantly in linked list and sorting problems. The dummy node technique simplifies any problem where you build a new list. The merge step is the heart of merge sort and appears in every divide-and-conquer sorting problem.

Once you have merge two sorted lists down, you are ready for Merge K Sorted Lists (#23), which simply calls this merge repeatedly (or uses a heap). You are also prepared for Sort List (#148), which applies merge sort to a linked list and uses this exact merge step as its core subroutine.

Practice this problem until you can write both the iterative and recursive solutions without hesitation. Then drill the pattern with YeetCode flashcards so it stays fresh for your next interview.