Merge Two Sorted Lists | Leetcode 21

Welcome to our deep dive on Merge Two Sorted Lists (Leetcode 21). This is the absolute paramount introductory linked list problem, teaching the essential Dummy Node pattern.

Problem Statement

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

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example: list1 = [1,2,4], list2 = [1,3,4] => Output: [1,1,2,3,4,4]

Approach: Two Pointers + Dummy Node O(N + M)

Because both input lists are entirely guaranteed to already be sorted, we can safely just compare their respective head nodes. Whichever is smaller becomes the next node in our merged list!

1. Create a dummy node. This effortlessly anchors the very start of our new list so we don't have to write edge cases for null heads.
2. Maintain a curr pointer starting at dummy.
3. Loop while both list1 and list2 are not null.
   • If list1.val <= list2.val, point curr.next to list1, and advance list1.
   • Else, point curr.next to list2, and advance list2.
   • Always advance curr forward!
4. Once the loop ends, one of the lists might still have leftover nodes. Because they are already sorted, we can just attach the entire remainder of that list directly to curr.next!

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
            
        # Attach any remaining elements
        curr.next = list1 if list1 else list2
        
        return dummy.next

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (21)