Merge Two Sorted Lists

How to Merge two sorted lists

Merging two sorted lists is one of the most fundamental problems in data structures, especially when working with linked lists. It’s a classic interview problem frequently asked by top tech companies like FAANG. The objective is to merge two sorted linked lists into a single sorted list, preserving the order of elements.

This lesson answers common questions like:

• How do you merge two sorted linked lists in Python?
• Which method is better: recursive or iterative?
• Can you merge two lists without using extra space?

Let’s explore the best strategies to solve this challenge with optimized code, step-by-step explanations, and practical insights.

What Does It Mean to Merge Two Sorted Linked Lists?

When we say merge two sorted linked lists, we mean combining two singly linked lists where elements are in increasing order into a new single list that maintains the sorted order. Each list contains nodes connected through pointers, and the merge process requires comparing the node values and re-linking the nodes accordingly.

Example:
List A: 1 -> 3 -> 5
List B: 2 -> 4 -> 6
Merged Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

The goal is to do this efficiently — ideally without allocating extra memory for new nodes.

Why Is This Problem Frequently Asked in Interviews?

This problem checks your understanding of:

• Linked list traversal
• Comparison logic
• Efficient use of pointers
• Implementing recursive vs. iterative solutions
• Time and space complexity awareness

It also mirrors real-world use cases like merging sorted data streams, implementing merge sort, or combining two sorted search results.

Hiring managers love this question because it reveals how well you understand in-place list manipulation and whether you can handle edge cases gracefully.

Different Approaches to Merge Two Sorted Lists

There are two primary ways to solve this problem:

1. Iterative Method

This approach uses a while loop and a dummy node technique to merge the lists node by node.

Advantages:

• Easy to debug
• No risk of stack overflow

Iterative Method Explanation:

• Initialize a dummy node to act as the head of the merged list.
• Use a pointer (current) to build the merged list.
• Traverse both lists, always attaching the node with the smaller value.
• Once one list ends, link the rest of the other list.

This method performs well with O(n + m) time and O(1) space.

2. Recursive Method

This method simplifies the problem using recursion and base cases.

Advantages:

• Concise and elegant
• Mirrors the problem structure naturally

Recursive Method Explanation:

• Base case: if one list is None, return the other.
• Compare the head nodes of both lists.
• The smaller node becomes the head, and its .next points to the merged result of the remaining lists.

Though elegant, recursion uses O(n + m) stack space, making it less memory-efficient for large lists.

Python Code for Merging Two Sorted Linked Lists

Let’s look at both methods in clean, well-commented Python code:

Iterative Approach (Python):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1, list2):
    dummy = ListNode()
    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
    
    current.next = list1 if list1 else list2
    return dummy.next

Recursive Approach (Python):

1
2
3
4
5
6
7
8
9
10
11
12
def mergeTwoLists(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1
    
    if list1.val < list2.val:
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
    else:
        list2.next = mergeTwoLists(list1, list2.next)
        return list2

Time and Space Complexity Analysis

Iterative Method:

• Time Complexity: O(n + m), where n and m are the lengths of the two sorted linked lists.
• Space Complexity: O(1), as no additional memory is used aside from a few pointers.

Recursive Method:

• Time Complexity: O(n + m), since every node from both lists is visited once.
• Space Complexity: O(n + m), due to the recursive call stack.

Handling Edge Cases

Be sure to account for:

• Both lists are empty → return None
• One list is empty → return the non-empty list
• Lists with repeated values → allow duplicates in the merged result

Robust code gracefully handles null inputs and avoids null pointer exceptions.

In-Place Merge vs New List Allocation

Both approaches reuse nodes from the input lists, making them in-place.
You are not creating new nodes—just rearranging the .next pointers, which leads to better memory optimization.

This is crucial when asked:
“Can we merge two linked lists without allocating additional memory?”
Answer: Yes, by reusing existing nodes and carefully adjusting pointers.

Visualization of the Merge Process

Understanding the flow helps:

Before:
List1 → 1 -> 4 -> 7
List2 → 2 -> 3 -> 5

During merge:
1 -> 2 -> 3 -> 4 -> 5 -> 7 (Node by node comparison and re-linking)

Visualizing helps reinforce pointer flow and node connections.

Common Mistakes and How to Avoid Them

Avoid these errors:

• Forgetting to move pointers: Leads to infinite loops.
• Returning incorrect node: Always return dummy.next for iterative.
• Losing node references: Always store .next before reassigning.

Debugging tips:

• Print pointers at each step
• Use diagrams to track node states

Related Problems to Practice

After mastering this problem, try these:

• Merge K Sorted Lists
• Sort a Linked List
• Remove Duplicates from a Sorted List
• Reverse a Linked List
• Intersection of Two Linked Lists

Conclusion

Merging two sorted linked lists is a foundational topic in linked list algorithms, testing your ability to manipulate pointers, understand recursion, and optimize for time and space. Whether you're solving it using a dummy node technique or elegant recursion, both methods are vital for mastering interview questions and real-world data processing.