Merge Two Sorted Lists

Merge two sorted linked lists into one sorted linked list

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

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

Merge the two lists in a 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.

Input/Output Specifications

Input: Two sorted linked lists
Output: Head of merged sorted linked list
Constraints:
- The number of nodes in both lists is in the range [0, 50]
- -100 <= Node.val <= 100
- Both list1 and list2 are sorted in non-decreasing order

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Solutions

Approach 1: Iterative (Two Pointers)

This approach uses two pointers to traverse both lists simultaneously and merge them by comparing values and linking nodes in sorted order.

Algorithm:

Create a dummy head node to simplify edge cases
Use a current pointer to build the merged list
Compare values from both lists and link the smaller one
Move the pointer of the list from which we took the node
Continue until one list is exhausted
Link the remaining nodes from the non-empty list
Return the head of the merged list (skip dummy)

Python:

def mergeTwoLists(list1, list2):
    """
    Merge two sorted linked lists iteratively
    Time: O(n + m)
    Space: O(1)
    """
    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
    
    # Link remaining nodes
    current.next = list1 if list1 else list2
    
    return dummy.next

Java:

class Solution {
    /**
     * Merge two sorted linked lists iteratively
     * Time: O(n + m)
     * Space: O(1)
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        
        // Link remaining nodes
        current.next = (list1 != null) ? list1 : list2;
        
        return dummy.next;
    }
}

Go:

// mergeTwoLists - Merge two sorted linked lists iteratively
// Time: O(n + m)
// Space: O(1)
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    current := dummy
    
    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            current.Next = list1
            list1 = list1.Next
        } else {
            current.Next = list2
            list2 = list2.Next
        }
        current = current.Next
    }
    
    // Link remaining nodes
    if list1 != nil {
        current.Next = list1
    } else {
        current.Next = list2
    }
    
    return dummy.Next
}

JavaScript:

/**
 * Merge two sorted linked lists iteratively
 * Time: O(n + m)
 * Space: O(1)
 */
function mergeTwoLists(list1, list2) {
    const dummy = new ListNode(0);
    let current = dummy;
    
    while (list1 !== null && list2 !== null) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    // Link remaining nodes
    current.next = list1 !== null ? list1 : list2;
    
    return dummy.next;
}

C#:

public class Solution {
    /// <summary>
    /// Merge two sorted linked lists iteratively
    /// Time: O(n + m)
    /// Space: O(1)
    /// </summary>
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        
        // Link remaining nodes
        current.next = list1 ?? list2;
        
        return dummy.next;
    }
}

Approach 2: Recursive

This approach uses recursion to merge the lists by comparing the first nodes and recursively merging the rest.

Algorithm:

Base case: if one list is empty, return the other
Compare the first nodes of both lists
Choose the smaller node as the current node
Recursively merge the rest of the lists
Return the head of the merged list

Python:

def mergeTwoListsRecursive(list1, list2):
    """
    Merge two sorted linked lists recursively
    Time: O(n + m)
    Space: O(n + m) - due to recursion stack
    """
    if not list1:
        return list2
    if not list2:
        return list1
    
    if list1.val <= list2.val:
        list1.next = mergeTwoListsRecursive(list1.next, list2)
        return list1
    else:
        list2.next = mergeTwoListsRecursive(list1, list2.next)
        return list2

Java:

class Solution {
    /**
     * Merge two sorted linked lists recursively
     * Time: O(n + m)
     * Space: O(n + m) - due to recursion stack
     */
    public ListNode mergeTwoListsRecursive(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        
        if (list1.val <= list2.val) {
            list1.next = mergeTwoListsRecursive(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoListsRecursive(list1, list2.next);
            return list2;
        }
    }
}

Go:

// mergeTwoListsRecursive - Merge two sorted linked lists recursively
// Time: O(n + m)
// Space: O(n + m) - due to recursion stack
func mergeTwoListsRecursive(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }
    if list2 == nil {
        return list1
    }
    
    if list1.Val <= list2.Val {
        list1.Next = mergeTwoListsRecursive(list1.Next, list2)
        return list1
    } else {
        list2.Next = mergeTwoListsRecursive(list1, list2.Next)
        return list2
    }
}

JavaScript:

/**
 * Merge two sorted linked lists recursively
 * Time: O(n + m)
 * Space: O(n + m) - due to recursion stack
 */
function mergeTwoListsRecursive(list1, list2) {
    if (list1 === null) {
        return list2;
    }
    if (list2 === null) {
        return list1;
    }
    
    if (list1.val <= list2.val) {
        list1.next = mergeTwoListsRecursive(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoListsRecursive(list1, list2.next);
        return list2;
    }
}

C#:

public class Solution {
    /// <summary>
    /// Merge two sorted linked lists recursively
    /// Time: O(n + m)
    /// Space: O(n + m) - due to recursion stack
    /// </summary>
    public ListNode MergeTwoListsRecursive(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        
        if (list1.val <= list2.val) {
            list1.next = MergeTwoListsRecursive(list1.next, list2);
            return list1;
        } else {
            list2.next = MergeTwoListsRecursive(list1, list2.next);
            return list2;
        }
    }
}

Key Insights

Dummy node technique: Using a dummy head simplifies edge cases and pointer management
Two-pointer approach: Compare and link nodes from both lists in sorted order
In-place merging: We reuse existing nodes rather than creating new ones
Recursive pattern: Elegant solution that mirrors the iterative approach
Stable merge: Maintains the relative order of equal elements

Edge Cases

One or both lists are empty
Lists with different lengths
Lists with duplicate values
Single node lists
Lists where all elements of one list are smaller than the other

Test Cases

# Test case 1: Normal case
list1 = ListNode(1)
list1.next = ListNode(2)
list1.next.next = ListNode(4)

list2 = ListNode(1)
list2.next = ListNode(3)
list2.next.next = ListNode(4)
# Expected: [1,1,2,3,4,4]

# Test case 2: One empty list
list3 = None
list4 = ListNode(0)
# Expected: [0]

# Test case 3: Both empty
list5 = None
list6 = None
# Expected: []

# Test case 4: Different lengths
list7 = ListNode(1)
list8 = ListNode(2)
list8.next = ListNode(3)
# Expected: [1,2,3]

Follow-up Questions

How would you merge k sorted linked lists?
Can you merge the lists without using extra space?
How would you handle merging with custom comparison functions?
What if the lists are not sorted?

Common Mistakes

Not handling empty list cases properly
Forgetting to link remaining nodes after the main loop
Incorrect pointer updates in the iterative approach
Stack overflow in recursive approach for very long lists
Not using dummy node to simplify edge cases
Memory leaks when not properly managing pointers