Merge Two Sorted Lists: Multiple Solutions and Complexity Analysis

Understanding the Problem: Merge Two Sorted Lists

Merging two sorted lists is one of the most fundamental operations in computer science. The problem appears in countless technical interviews, forms the backbone of the Merge Sort algorithm, and has practical applications in data processing, database indexing, and stream processing. At its core, the challenge is deceptively simple: given two sorted sequences (linked lists, arrays, or any ordered collection), produce a single sorted sequence that contains all elements from both inputs.

Problem Statement (Linked List Version)

Given the heads of two sorted singly-linked lists list1 and list2, merge them into one sorted linked list and return its head. The merged list must be composed by splicing together the nodes of the original lists. Both input lists are sorted in non-decreasing order.

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

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

Example 3:
Input: list1 = [], list2 = []
Output: []

Array Version

When working with arrays, the problem takes a slightly different form. You have two sorted arrays arr1 and arr2 of lengths m and n respectively. The goal is to produce a merged sorted array. A common variant asks you to merge arr2 into arr1 in-place, where arr1 has enough extra space at the end to accommodate all elements.

Why This Problem Matters

Mastering the merge of sorted lists is essential for several reasons:

• Foundation of Merge Sort: The merge operation is the core subroutine of merge sort, one of the most important O(n log n) sorting algorithms. Understanding merging deeply helps you implement and optimize merge sort confidently.
• Pointer Manipulation: In the linked list variant, you practice critical pointer manipulation skills — reassigning next pointers, handling edge cases, and managing iteration without losing references.
• Stream Processing: Merging sorted streams is a common pattern in systems that process ordered data from multiple sources, such as log aggregation, event processing, and database merge joins.
• Technical Interviews: This problem is among the most frequently asked questions at companies like Google, Meta, Amazon, and Microsoft. It tests your understanding of linked lists, recursion, iteration, and edge case handling all in one go.
• In-Place Algorithms: The array variant teaches space optimization — how to perform merging without allocating extra memory, a crucial skill for embedded systems and high-performance computing.

Solution Approaches for Linked Lists

Let's explore four distinct approaches to merging sorted linked lists, each with different trade-offs in terms of readability, space complexity, and real-world applicability. We'll use Python for our examples, but the concepts transfer seamlessly to Java, C++, JavaScript, and other languages.

Approach 1: Brute Force — Collect, Sort, Rebuild

The simplest mental model is to extract all values from both lists into a Python list, sort them using the built-in sort, and then reconstruct a new linked list from the sorted values. While not the most efficient in terms of space or pointer reuse, this approach is easy to understand and works correctly in all cases.

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

def mergeTwoLists_brute(list1, list2):
    # Step 1: Collect all values
    values = []
    curr = list1
    while curr:
        values.append(curr.val)
        curr = curr.next
    curr = list2
    while curr:
        values.append(curr.val)
        curr = curr.next
    
    # Step 2: Sort the collected values
    values.sort()
    
    # Step 3: Rebuild the linked list
    dummy = ListNode(0)
    curr = dummy
    for v in values:
        curr.next = ListNode(v)
        curr = curr.next
    
    return dummy.next

# Time Complexity: O((m+n) log(m+n)) due to sorting
# Space Complexity: O(m+n) for the values array + O(m+n) for the new linked list nodes

Analysis: This approach discards the advantage that the input lists are already sorted. The sorting step dominates with O((m+n) log(m+n)) time, compared to the optimal O(m+n). It also creates entirely new nodes rather than reusing existing ones. However, for small inputs or rapid prototyping, this method is straightforward and hard to get wrong.

Approach 2: Two Pointers — Iterative Merge (Optimal)

This is the classic, most efficient solution. We maintain two pointers — one for each input list — and a tail pointer for building the merged list. At each step, we compare the current nodes, attach the smaller one to the merged list, and advance the corresponding pointer. A dummy head node simplifies edge cases.

def mergeTwoLists_iterative(list1, list2):
    # Dummy node serves as the start of the merged list
    dummy = ListNode(0)
    tail = dummy  # tail always points to the last node in the merged list
    
    # Traverse both lists, comparing nodes
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    
    # Attach the remaining nodes from whichever list is non-empty
    if list1:
        tail.next = list1
    elif list2:
        tail.next = list2
    
    return dummy.next

# Time Complexity: O(m + n) — we visit each node exactly once
# Space Complexity: O(1) — we only use a few pointers, no extra memory allocation

Step-by-step walkthrough:

• Initialize: Create a dummy node. Set tail = dummy. The dummy node's next will eventually point to the head of the merged list.
• Loop: While both list1 and list2 are non-null, compare list1.val and list2.val. Attach the smaller node to tail.next, advance that list's pointer, and move tail forward.
• Cleanup: After the loop, at most one list still has nodes. Attach the entire remainder to tail.next.
• Return: Return dummy.next as the head of the merged list.

This solution is optimal in both time and space, reuses the original nodes, and is the gold standard for interviews and production code.

Approach 3: Recursive Merge

The recursive solution leverages the fact that merging two sorted lists has a natural recursive structure. The smaller head becomes the head of the merged list, and its next pointer is set to the result of recursively merging the rest of that list with the other list. This approach produces elegant, concise code but uses stack space proportional to the total length of the lists.

def mergeTwoLists_recursive(list1, list2):
    # Base cases: if either list is empty, return the other
    if not list1:
        return list2
    if not list2:
        return list1
    
    # Recursive case: pick the smaller head and recurse
    if list1.val <= list2.val:
        list1.next = mergeTwoLists_recursive