Merge Two Sorted Lists: A Step-by-Step Guide

Algorithm Updated on April 16, 2025

Table of Contents

  1. Introduction
  2. Problem Statement
  3. Iterative Solution in Python
  4. Test Cases
  5. Time and Space Complexity
  6. Key Takeaways
  7. Conclusion

Introduction

The Merge Two Sorted Lists problem is a staple in coding interviews, often used to evaluate a candidate’s understanding of linked list manipulation and algorithmic thinking. It requires merging two sorted linked lists into a single sorted linked list while maintaining the sorted order. This post will guide you through the problem, provide a clean Python solution, and include test cases to ensure correctness.

Problem Statement

You are given the heads of two sorted linked lists, list1 and list2. Your task is to merge them into one sorted linked list and return its head. The lists are sorted in non-decreasing (ascending) order, and the merged list must also be sorted.

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • Node values are integers in the range [-100, 100].

Example:

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

Iterative Solution in Python

The iterative approach is the most intuitive and space-efficient way to solve this problem. It uses a dummy node to simplify the merging process and a pointer to build the merged list.

Here’s the Python code:

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

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy

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

    # Attach remaining nodes, if any
    current.next = list1 if list1 else list2

    return dummy.next

How It Works

  1. Dummy Node: We create a dummy node to act as the starting point of the merged list, avoiding edge cases when initializing the head.
  2. Current Pointer: The current pointer builds the merged list by linking nodes.
  3. Comparison: While both lists have nodes, we compare their current values:
    • If list1.val <= list2.val, attach list1 to current.next and advance list1.
    • Otherwise, attach list2 and advance list2.
    • Move current to the newly attached node.
  4. Remaining Nodes: If one list is exhausted, attach the remaining nodes of the other list.
  5. Return: Return dummy.next as the head of the merged list.

Test Cases

To verify the solution, we’ll write test cases that cover various scenarios, including empty lists, single-node lists, and lists with duplicates.

def createLinkedList(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

def linkedListToList(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# Test cases
def test_mergeTwoLists():
    # Test Case 1: Normal case
    list1 = createLinkedList([1, 2, 4])
    list2 = createLinkedList([1, 3, 4])
    result = mergeTwoLists(list1, list2)
    assert linkedListToList(result) == [1, 1, 2, 3, 4, 4], "Test Case 1 Failed"

    # Test Case 2: Both empty
    list1 = createLinkedList([])
    list2 = createLinkedList([])
    result = mergeTwoLists(list1, list2)
    assert linkedListToList(result) == [], "Test Case 2 Failed"

    # Test Case 3: One empty
    list1 = createLinkedList([])
    list2 = createLinkedList([0])
    result = mergeTwoLists(list1, list2)
    assert linkedListToList(result) == [0], "Test Case 3 Failed"

    # Test Case 4: Single node lists
    list1 = createLinkedList([1])
    list2 = createLinkedList([2])
    result = mergeTwoLists(list1, list2)
    assert linkedListToList(result) == [1, 2], "Test Case 4 Failed"

    print("All test cases passed!")

# Run tests
test_mergeTwoLists()

Explanation of Test Cases

  • Test Case 1: Merges [1,2,4] and [1,3,4], expecting [1,1,2,3,4,4].
  • Test Case 2: Merges two empty lists, expecting [].
  • Test Case 3: Merges an empty list with [0], expecting [0].
  • Test Case 4: Merges single-node lists [1] and [2], expecting [1,2].

The helper functions createLinkedList and linkedListToList simplify creating and validating linked lists.

Time and Space Complexity

  • Time Complexity: O(n + m), where n and m are the lengths of list1 and list2. We traverse each node exactly once.
  • Space Complexity: O(1), as we only use a few pointers (dummy and current) regardless of input size. The merged list reuses existing nodes.

Key Takeaways

  1. Use a Dummy Node: It simplifies edge cases, especially when dealing with the head of the merged list.
  2. Handle Edge Cases: Always account for empty lists or lists of different lengths.
  3. Practice Pointer Manipulation: This problem is a great way to master linked list traversal and pointer updates.
  4. Iterative vs. Recursive: The iterative solution is often preferred in interviews due to its O(1) space complexity.

Conclusion

The Merge Two Sorted Lists problem is an excellent exercise for honing your linked list skills and preparing for coding interviews. By using an iterative approach with a dummy node, you can efficiently merge two sorted lists with minimal space overhead. The provided Python code and test cases ensure correctness across various scenarios. Practice this problem, experiment with the recursive approach, and try related problems like Merge k Sorted Lists to deepen your understanding. Happy coding!