21. Merge Two Sorted Lists - Explanation

Problem Link

Description

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted linked list and return the head of the new sorted linked list.

The new list should be made up of nodes from list1 and list2.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,5]

Output: [1,1,2,3,4,5]

Example 2:

Input: list1 = [], list2 = [1,2]

Output: [1,2]

Example 3:

Input: list1 = [], list2 = []

Output: []

Constraints:

• 0 <= The length of the each list <= 100.
• -100 <= Node.val <= 100

Recommended Time & Space Complexity

You should aim for a solution with O(n + m) time and O(1) space, where n is the length of list1 and m is the length of list2.

Hint 1

A brute force solution would involve storing the values of both linked lists in an array, sorting the array, and then converting it back into a linked list. This approach would use O(n) extra space and is trivial. Can you think of a better way? Perhaps the sorted nature of the lists can be leveraged.

Hint 2

We create a dummy node to keep track of the head of the resulting linked list while iterating through the lists. Using l1 and l2 as iterators for list1 and list2, respectively, we traverse both lists node by node to build a final linked list that is also sorted. How do you implement this?

Hint 3

For example, consider list1 = [1, 2, 3] and list2 = [2, 3, 4]. While iterating through the lists, we move the pointers by comparing the node values from both lists. We link the next pointer of the iterator to the node with the smaller value. For instance, when l1 = 1 and l2 = 2, since l1 < l2, we point the iterator's next pointer to l1 and proceed.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

Merging two sorted linked lists recursively works by always choosing the smaller head node of the two lists.
Whichever list has the smaller value should appear first in the merged list.
So we:

• Pick the smaller node.
• Recursively merge the rest of the lists.
• Attach the result to the chosen node.

Algorithm

1. If one list is empty, return the other list — nothing left to merge.
2. Compare the head values of list1 and list2:
   • If list1.val <= list2.val:
     • Set list1.next to the merged result of the remaining nodes.
     • Return list1 as the current head.
   • Otherwise:
     • Set list2.next to the merged result of the remaining nodes.
     • Return list2 as the current head.
3. The recursion continues until both lists are fully merged.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        if list2 is None:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n + m)$

Where $n$ is the length of $list1$ and $m$ is the length of $list2$.

---

2. Iteration

Intuition

To merge two sorted linked lists iteratively, we build the result step-by-step.
We keep a pointer (node) to the current end of the merged list, and at each step we choose the smaller head node from list1 or list2.

Because the lists are already sorted, whichever head is smaller must come next in the merged list.
We attach that node, move the pointer forward, and continue until one list is empty.
Finally, we attach the remaining nodes from the non-empty list.

Using a dummy node makes handling the head of the merged list simple and clean.

Algorithm

1. Create a dummy node and a node pointer pointing to it.
2. While both lists have nodes:
   • Compare list1.val and list2.val.
   • Attach the smaller node to node.next.
   • Move forward in the chosen list.
   • Move node to node.next.
3. When one list becomes empty:
   • Attach the remaining nodes of the other list to node.next.
4. Return dummy.next, which is the head of the merged list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = node = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                node.next = list1
                list1 = list1.next
            else:
                node.next = list2
                list2 = list2.next
            node = node.next

        node.next = list1 or list2

        return dummy.next

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(1)$

Where $n$ is the length of $list1$ and $m$ is the length of $list2$.

---

Common Pitfalls

Forgetting to Handle Empty Lists

A common mistake is not checking if one or both input lists are null/None before starting the merge. If list1 is empty, the answer is simply list2, and vice versa. Failing to handle these edge cases leads to null pointer exceptions or incorrect results.

Not Attaching the Remaining Nodes

After the main comparison loop ends, one list may still have remaining nodes. A frequent error is forgetting to attach these leftover nodes to the merged list. Since both lists are sorted, simply linking the remaining portion to the end of the merged list completes the merge correctly.