LeetCode 21 - Merge Two Sorted Lists

This Easy problem merges two sorted linked lists into one sorted list. I compared the current nodes, linked the smaller one to the result, and used a dummy node so the first insertion follows the same logic as every later insertion.

---

Problem link and explanation

• Problem: 21. Merge Two Sorted Lists
• Summary: Given the heads of two sorted linked lists, connect their existing nodes in ascending order and return the head of the merged list.

Because both inputs are already sorted, only their current nodes need to be compared. Linking the smaller node and advancing that list selects the smallest unprocessed value at every step.

---

Approach

I created a dummy node whose value has no role in the result. The curr pointer tracks the last node in the merged list.

dummy = ListNode()
curr = dummy

While both lists still contain nodes, the smaller current node is attached to curr.next. The pointer for the selected list advances, followed by curr.

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

When the loop ends, one list has been exhausted. The remaining list is already sorted, so its entire tail can be attached directly.

curr.next = list1 if list1 else list2

The dummy node is only an implementation aid. The actual head of the merged list is dummy.next.

---

Troubleshooting

An initially empty input does not need a separate branch. The loop is skipped, and the nonempty list is attached directly to curr.next. If both inputs are empty, that assignment and the final return both produce None.

The return value must also exclude the dummy node. Returning dummy would add an artificial node to the result, while dummy.next points to the first node selected from the inputs.

---

Complexity analysis

• Time complexity: O(n + m)
  • Each node from both lists is inspected and linked at most once.
• Space complexity: O(1)
  • The algorithm rewires existing next pointers and does not allocate a data structure that grows with the input.

---

Implementation code

from typing import Optional

class Solution:
    def mergeTwoLists(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy

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

        curr.next = list1 if list1 else list2

        return dummy.next

---

Summary and reflection

The sorted inputs make the local comparison sufficient: selecting the smaller current node preserves the global order. A dummy node removes the special case for initializing the result head, and attaching the remaining tail avoids an unnecessary second traversal.