Merge Two Sorted Lists

How it works

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.

Steps

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.

Complexity

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

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

Things to watch for

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.

# 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* node = &dummy;

        while (list1 && list2) {
            if (list1->val < list2->val) {
                node->next = list1;
                list1 = list1->next;
            } else {
                node->next = list2;
                list2 = list2->next;
            }
            node = node->next;
        }

        if (list1) {
            node->next = list1;
        } else {
            node->next = list2;
        }

        return dummy.next;
    }
};