LeetCode 21: Merge Two Sorted Lists Solution in Python Explained

Problem Statement

LeetCode 21, Merge Two Sorted Lists, is an easy-level challenge where you’re given the heads of two sorted linked lists, list1 and list2, and need to merge them into one sorted linked list. The lists are sorted in non-decreasing order, and you must return the head of the merged list. Each node contains an integer value and a pointer to the next node, and the lists can be empty.

Constraints

  • Number of nodes in both lists is between 0 and 50.
  • -100 <= Node.val <= 100: Node values range from -100 to 100.
  • Both lists are sorted in non-decreasing order.

Example

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Explanation: Merge into one sorted list.

Input: list1 = [], list2 = []
Output: []
Explanation: Both empty, return empty list.

Input: list1 = [], list2 = [0]
Output: [0]
Explanation: Merge empty with [0], return [0].

Understanding the Problem

How do you solve LeetCode 21: Merge Two Sorted Lists in Python? Imagine you have two sorted lists like [1,2,4] and [1,3,4]. You need to combine them into a single sorted list, [1,1,2,3,4,4], by comparing nodes and linking them in order. Since they’re linked lists, we’ll traverse them with pointers, building the merged list step-by-step or recursively. We’ll explore two approaches: an Iterative solution (using pointers) and a Recursive solution (using function calls).

Solution 1: Iterative Approach (Primary)

Explanation

Use a dummy node and a pointer to build the merged list iteratively. Compare nodes from both lists, linking the smaller value, and move forward until both lists are exhausted.

Here’s a visual for merging [1,2] and [3,4]:

list1: 1 -> 2
list2: 3 -> 4
Merged: dummy -> 1 -> 2 -> 3 -> 4
  1. Create Dummy Node.
  • Start with a dummy node to simplify linking.
  1. Initialize Pointer.
  • Use a current pointer starting at dummy.
  1. Compare and Link.
  • While both lists have nodes, compare values, link the smaller, move forward.
  1. Handle Remaining Nodes.
  • Append any leftover nodes from either list.
  1. Return Head.
  • Return dummy.next as the merged list head.

Step-by-Step Example

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

We have [1,2,4] and [1,3,4], aiming for [1,1,2,3,4,4].

  • Goal: Merge into one sorted list.
  • Result for Reference: [1,1,2,3,4,4].
  • Start: Dummy node created, current points to dummy.
  • Step 1: Compare list1 (1) and list2 (1).
    • list1.val = 1, list2.val = 1, choose list1 (arbitrary).
    • current.next = list1 (1), list1 moves to 2.
    • Current moves to 1, list: dummy -> 1.
  • Step 2: Compare list1 (2) and list2 (1).
    • list2.val = 1 < 2, choose list2.
    • current.next = list2 (1), list2 moves to 3.
    • Current to 1, list: dummy -> 1 -> 1.
  • Step 3: Compare list1 (2) and list2 (3).
    • list1.val = 2 < 3, choose list1.
    • current.next = list1 (2), list1 moves to 4.
    • Current to 2, list: dummy -> 1 -> 1 -> 2.
  • Step 4: Compare list1 (4) and list2 (3).
    • list2.val = 3 < 4, choose list2.
    • current.next = list2 (3), list2 moves to 4.
    • Current to 3, list: dummy -> 1 -> 1 -> 2 -> 3.
  • Step 5: Compare list1 (4) and list2 (4).
    • list1.val = 4 = list2.val, choose list1.
    • current.next = list1 (4), list1 moves to null.
    • Current to 4, list: dummy -> 1 -> 1 -> 2 -> 3 -> 4.
  • Step 6: list1 empty, list2 has 4.
    • current.next = list2 (4), list2 moves to null.
    • List: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4.
  • Step 7: Both lists empty.
    • Return dummy.next.
  • Finish: [1,1,2,3,4,4].

Example 2: list1 = [], list2 = [0]

Now, [] and [0].

  • Goal: Merge into sorted list.
  • Result for Reference: [0].
  • Start: Dummy node, current at dummy.
  • Step 1: list1 empty, list2 = [0].
    • current.next = list2 (0), list2 moves to null.
    • List: dummy -> 0.
  • Step 2: Both empty.
    • Return dummy.next.
  • Finish: [0].

How the Code Works (Iterative)

Here’s the Python code with line-by-line explanation:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    # Line 1: Create dummy node to simplify linking
    dummy = ListNode(0)
    # Line 2: Set current pointer to dummy for building list
    current = dummy

    # Line 3: Loop while both lists have nodes
    while list1 and list2:
        # Line 4: Compare values, choose smaller (or equal)
        if list1.val <= list2.val:
            # Line 5: Link current to list1 node
            current.next = list1
            # Line 6: Move list1 to next node
            list1 = list1.next
        else:
            # Line 7: Link current to list2 node
            current.next = list2
            # Line 8: Move list2 to next node
            list2 = list2.next
        # Line 9: Move current pointer forward
        current = current.next

    # Line 10: If list1 has nodes left, append them
    if list1:
        current.next = list1
    # Line 11: If list2 has nodes left, append them
    if list2:
        current.next = list2

    # Line 12: Return head of merged list
    return dummy.next

Alternative: Recursive Approach

Explanation

Recursively merge by choosing the smaller head node and linking it to the result of merging the remaining nodes.

  1. Base Cases.
  • If list1 empty, return list2; if list2 empty, return list1.
  1. Choose Smaller Head.
  • Compare heads, use smaller as root.
  1. Recurse.
  • Link root.next to result of merging remaining nodes.
  1. Return Root.
  • Return head of merged list.

Step-by-Step Example (Recursive)

For list1 = [1,2,4], list2 = [1,3,4]:

  • Goal: Merge into [1,1,2,3,4,4].
  • Result for Reference: [1,1,2,3,4,4].
  • Step 1: Call merge(list1=1->2->4, list2=1->3->4).
    • list1.val = 1 ≤ list2.val = 1, choose list1.
    • list1.next = merge(2->4, 1->3->4).
  • Step 2: merge(2->4, 1->3->4).
    • 2 > 1, choose list2.
    • list2.next = merge(2->4, 3->4).
  • Step 3: merge(2->4, 3->4).
    • 2 < 3, choose list1.
    • list1.next = merge(4, 3->4).
  • Step 4: merge(4, 3->4).
    • 4 > 3, choose list2.
    • list2.next = merge(4, 4).
  • Step 5: merge(4, 4).
    • 4 ≤ 4, choose list1.
    • list1.next = merge(null, 4).
  • Step 6: merge(null, 4).
    • list1 empty, return list2 (4).
  • Step 7: Build back.
    • 4->4, 3->4->4, 2->3->4->4, 1->2->3->4->4, 1->1->2->3->4->4.
  • Finish: Return [1,1,2,3,4,4].

How the Code Works (Recursive)

Here’s the recursive Python code with explanations:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoListsRecursive(list1: ListNode, list2: ListNode) -> ListNode:
    # Line 1: If list1 empty, return list2
    if not list1:
        return list2
    # Line 2: If list2 empty, return list1
    if not list2:
        return list1

    # Line 3: Compare head values
    if list1.val <= list2.val:
        # Line 4: Use list1 as root
        root = list1
        # Line 5: Recursively merge list1.next with list2
        root.next = mergeTwoListsRecursive(list1.next, list2)
    else:
        # Line 6: Use list2 as root
        root = list2
        # Line 7: Recursively merge list1 with list2.next
        root.next = mergeTwoListsRecursive(list1, list2.next)

    # Line 8: Return root of merged list
    return root

Complexity

  • Iterative:
    • Time: O(n + m) – Single pass through both lists, where n and m are lengths.
    • Space: O(1) – Only uses pointers.
  • Recursive:
    • Time: O(n + m) – Recursion depth equals total nodes.
    • Space: O(n + m) – Recursion stack space.

Efficiency Notes

Both methods are O(n + m) in time, but iterative uses O(1) space, making it more space-efficient. Recursive is elegant but uses stack space, which could matter for very long lists.

Key Insights

Tips to master LeetCode 21:

  • Dummy Simplifies: Iterative needs a dummy for edge cases—don’t skip it!
  • Compare and Move: Both methods rely on comparing heads and advancing.
  • Recursion Shines: Recursive is concise if stack space isn’t a concern.

Additional Example

For list1 = [5], list2 = [1,3]:

  • Goal: Merge to [1,3,5].
  • Iterative: Dummy -> 1 -> 3 -> 5.
  • Recursive: 1 -> merge(5, 3) -> 3 -> 5.
  • Result: [1,3,5].

Edge Cases

  • Both Empty: [], [] – Returns [].
  • One Empty: [], [1] – Returns [1].
  • Single Nodes: [1], [2] – Returns [1,2].

Final Thoughts

Both iterative and recursive methods solve LeetCode 21 efficiently in Python. Iterative is space-savvy, while recursive is elegant. Check LeetCode 19: Remove Nth Node for more linked list practice!