Merge Two Sorted Lists

Problem Statement

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a single sorted list. The list should be made by splicing together the nodes of the two lists.

Return the head of the merged linked list.

What to notice first

• You are working with linked lists, not arrays, so you cannot jump to arbitrary indices.
• Both input lists are already sorted, so you can decide which node to add next by simple comparison.
• You must use pointer manipulation; you cannot create new nodes (except for a dummy node to simplify code).
• The traversal pattern is similar to merging two sorted arrays, but with node pointers instead of indices.

Examples

list1	list2	Output	Explanation
[1, 2, 4]	[1, 3, 4]	[1, 1, 2, 3, 4, 4]	All six nodes merged in sorted order
[]	[]	[]	Both lists are empty
[]	[0]	[0]	First list is empty, return second 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.

Real-World Applications

Where this pattern appears

• File merging — combining two sorted file streams (log files, time-series data) into a single sorted output.
• Database operations — merging results from two sorted database queries or indexes.
• Merge sort implementation — the merge step of a divide-and-conquer sorting algorithm.
• Stream processing — combining two ordered event streams in real-time analytics.
• Playlist management — merging two chronologically sorted playlists into a unified timeline.

Complexity Comparison

Approach	Time	Space	Nodes Created	Best When
Iterative	O(m + n)	O(1)	Zero (reuse input nodes)	General case — clearer, no stack overhead
Recursive	O(m + n)	O(m + n)	Zero (reuse input nodes)	Learning recursion, practicing pointer manipulation

* Space refers to extra memory excluding the output list. Both approaches reuse nodes from the input lists.

Which approach should you learn first?

• Pick Iterative if you want the most efficient solution with minimal memory overhead.
• Pick Recursive if you are practicing recursion or want to understand the elegant elegance of self-similar problems.

Recommended

Iterative

O(m + n) time · O(1) space

Elegant

Recursive

O(m + n) time · O(m + n) space

Approach 1: Iterative (Recommended)

★ Recommended

Maintain a pointer to the tail of the merged list and step through both input lists, always appending the smaller node to the result.

The key idea is simple: maintain a tail pointer that points to the last node of the merged list. Compare the next nodes from both lists, append the smaller one, and advance its pointer. When one list is exhausted, append the entire remainder of the other list.

⏱ Time O(m + n) Single pass through both lists 💾 Space O(1) Only pointer variables

Step-by-step Example

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

Step	current.next	list1	list2	list1.val vs list2.val	Action
1	dummy	1	1	1 == 1 → choose list1	Attach list1 node (1), advance list1
2	1	2	1	2 > 1 → choose list2	Attach list2 node (1), advance list2
3	1	2	3	2 < 3 → choose list1	Attach list1 node (2), advance list1
4	2	4	3	4 > 3 → choose list2	Attach list2 node (3), advance list2
5	3	4	4	4 == 4 → choose list1	Attach list1 node (4), advance list1
6	4	null	4	list1 exhausted	Attach entire list2 (4)

Final Output: 1 → 1 → 2 → 3 → 4 → 4

Animated walkthrough

How the iterative solution merges two sorted lists

Watch the tail pointer move through both input lists, always choosing the smaller node at each step.

Back Autoplay Next Reset

Step 1 of 7 Target: merged

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function mergeTwoSortedListsIterative(list1, list2):
    dummy = new 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

    // Append remaining nodes
    if list1:
        current.next = list1
    else:
        current.next = list2

    return dummy.next

Solution Code

Python

merge_two_sorted_lists_iterative.py

from typing import Optional


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


def merge_two_sorted_lists_iterative(
    list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
    """
    Merge two sorted linked lists iteratively.

    Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
    Space Complexity: O(1) excluding the output list
    """
    # Create a dummy node to simplify the code
    dummy = ListNode(0)
    current = dummy

    # Traverse both lists and append the smaller node
    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

    # Append the remaining nodes
    if list1:
        current.next = list1
    else:
        current.next = list2

    return dummy.next


# Helper function to create a linked list from a list
def create_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Helper function to convert linked list to list for easy testing
def linked_list_to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result


# Test cases
list1 = create_linked_list([1, 2, 4])
list2 = create_linked_list([1, 3, 4])
result = merge_two_sorted_lists_iterative(list1, list2)
print(linked_list_to_list(result))  # [1, 1, 2, 3, 4, 4]

list1 = create_linked_list([])
list2 = create_linked_list([])
result = merge_two_sorted_lists_iterative(list1, list2)
print(linked_list_to_list(result))  # []

list1 = create_linked_list([])
list2 = create_linked_list([0])
result = merge_two_sorted_lists_iterative(list1, list2)
print(linked_list_to_list(result))  # [0]

C++

merge_two_sorted_lists_iterative.cpp

#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

/**
 * Merge two sorted linked lists iteratively.
 *
 * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
 * Space Complexity: O(1) excluding the output list
 */
ListNode* mergeTwoSortedListsIterative(ListNode* list1, ListNode* list2) {
    // Create a dummy node to simplify the code
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    // Traverse both lists and append the smaller node
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            current->next = list1;
            list1 = list1->next;
        } else {
            current->next = list2;
            list2 = list2->next;
        }
        current = current->next;
    }

    // Append the remaining nodes
    if (list1) {
        current->next = list1;
    } else {
        current->next = list2;
    }

    return dummy->next;
}

// Helper function to create a linked list from a vector
ListNode* createLinkedList(const vector<int>& values) {
    if (values.empty()) {
        return nullptr;
    }
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (size_t i = 1; i < values.size(); i++) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// Helper function to print linked list
void printLinkedList(ListNode* node) {
    cout << "[";
    while (node) {
        cout << node->val;
        if (node->next) cout << ", ";
        node = node->next;
    }
    cout << "]" << endl;
}

// Test cases
int main() {
    ListNode* list1 = createLinkedList({1, 2, 4});
    ListNode* list2 = createLinkedList({1, 3, 4});
    ListNode* result = mergeTwoSortedListsIterative(list1, list2);
    printLinkedList(result);  // [1, 1, 2, 3, 4, 4]

    list1 = createLinkedList({});
    list2 = createLinkedList({});
    result = mergeTwoSortedListsIterative(list1, list2);
    printLinkedList(result);  // []

    list1 = createLinkedList({});
    list2 = createLinkedList({0});
    result = mergeTwoSortedListsIterative(list1, list2);
    printLinkedList(result);  // [0]

    return 0;
}

Java

merge_two_sorted_lists_iterative.java

public class merge_two_sorted_lists_iterative {

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * Merge two sorted linked lists iteratively.
     *
     * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
     * Space Complexity: O(1) excluding the output list
     */
    public static ListNode mergeTwoSortedListsIterative(ListNode list1, ListNode list2) {
        // Create a dummy node to simplify the code
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Traverse both lists and append the smaller node
        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;
        }

        // Append the remaining nodes
        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }

        return dummy.next;
    }

    // Helper function to create a linked list from an array
    static ListNode createLinkedList(int[] values) {
        if (values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to print linked list
    static void printLinkedList(ListNode node) {
        System.out.print("[");
        boolean first = true;
        while (node != null) {
            if (!first) System.out.print(", ");
            System.out.print(node.val);
            first = false;
            node = node.next;
        }
        System.out.println("]");
    }

    // Test cases
    public static void main(String[] args) {
        ListNode list1 = createLinkedList(new int[]{1, 2, 4});
        ListNode list2 = createLinkedList(new int[]{1, 3, 4});
        ListNode result = mergeTwoSortedListsIterative(list1, list2);
        printLinkedList(result);  // [1, 1, 2, 3, 4, 4]

        list1 = createLinkedList(new int[]{});
        list2 = createLinkedList(new int[]{});
        result = mergeTwoSortedListsIterative(list1, list2);
        printLinkedList(result);  // []

        list1 = createLinkedList(new int[]{});
        list2 = createLinkedList(new int[]{0});
        result = mergeTwoSortedListsIterative(list1, list2);
        printLinkedList(result);  // [0]
    }
}

JavaScript

merge_two_sorted_lists_iterative.js

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Merge two sorted linked lists iteratively.
 *
 * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
 * Space Complexity: O(1) excluding the output list
 *
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
function mergeTwoSortedListsIterative(list1, list2) {
    // Create a dummy node to simplify the code
    const dummy = new ListNode(0);
    let current = dummy;

    // Traverse both lists and append the smaller node
    while (list1 && list2) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }

    // Append the remaining nodes
    current.next = list1 || list2;

    return dummy.next;
}

// Helper function to create a linked list from an array
function createLinkedList(values) {
    if (values.length === 0) {
        return null;
    }
    const head = new ListNode(values[0]);
    let current = head;
    for (let i = 1; i < values.length; i++) {
        current.next = new ListNode(values[i]);
        current = current.next;
    }
    return head;
}

// Helper function to convert linked list to array for testing
function linkedListToArray(node) {
    const result = [];
    while (node) {
        result.push(node.val);
        node = node.next;
    }
    return result;
}

// Test cases
let list1 = createLinkedList([1, 2, 4]);
let list2 = createLinkedList([1, 3, 4]);
let result = mergeTwoSortedListsIterative(list1, list2);
console.log(linkedListToArray(result));  // [1, 1, 2, 3, 4, 4]

list1 = createLinkedList([]);
list2 = createLinkedList([]);
result = mergeTwoSortedListsIterative(list1, list2);
console.log(linkedListToArray(result));  // []

list1 = createLinkedList([]);
list2 = createLinkedList([0]);
result = mergeTwoSortedListsIterative(list1, list2);
console.log(linkedListToArray(result));  // [0]

Rust

merge_two_sorted_lists_iterative.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

/**
 * Merge two sorted linked lists iteratively.
 *
 * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
 * Space Complexity: O(1) excluding the output list
 */
pub fn merge_two_sorted_lists_iterative(
    mut list1: Option<Box<ListNode>>,
    mut list2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    // Create a dummy node
    let mut dummy = Box::new(ListNode::new(0));
    let mut current = &mut dummy;

    // Traverse both lists and append the smaller node
    while let (Some(mut node1), Some(mut node2)) = (list1, list2) {
        if node1.val <= node2.val {
            list1 = node1.next.take();
            list2 = Some(node2);
            current.next = Some(node1);
        } else {
            list2 = node2.next.take();
            list1 = Some(node1);
            current.next = Some(node2);
        }
        current = current.next.as_mut().unwrap();
    }

    // Append the remaining nodes
    current.next = list1.or(list2);

    dummy.next
}

// Helper function to create a linked list from a vector
pub fn create_linked_list(values: Vec<i32>) -> Option<Box<ListNode>> {
    let mut head = None;
    for &val in values.iter().rev() {
        let mut node = Box::new(ListNode::new(val));
        node.next = head;
        head = Some(node);
    }
    head
}

// Helper function to convert linked list to vector for testing
pub fn linked_list_to_vec(mut node: Option<Box<ListNode>>) -> Vec<i32> {
    let mut result = Vec::new();
    while let Some(n) = node {
        result.push(n.val);
        node = n.next;
    }
    result
}

fn main() {
    let list1 = create_linked_list(vec![1, 2, 4]);
    let list2 = create_linked_list(vec![1, 3, 4]);
    let result = merge_two_sorted_lists_iterative(list1, list2);
    println!("{:?}", linked_list_to_vec(result));  // [1, 1, 2, 3, 4, 4]

    let list1 = create_linked_list(vec![]);
    let list2 = create_linked_list(vec![]);
    let result = merge_two_sorted_lists_iterative(list1, list2);
    println!("{:?}", linked_list_to_vec(result));  // []

    let list1 = create_linked_list(vec![]);
    let list2 = create_linked_list(vec![0]);
    let result = merge_two_sorted_lists_iterative(list1, list2);
    println!("{:?}", linked_list_to_vec(result));  // [0]
}

Go

merge_two_sorted_lists_iterative.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

/**
 * Merge two sorted linked lists iteratively.
 *
 * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
 * Space Complexity: O(1) excluding the output list
 */
func mergeTwoSortedListsIterative(list1 *ListNode, list2 *ListNode) *ListNode {
  // Create a dummy node to simplify the code
  dummy := &ListNode{Val: 0}
  current := dummy

  // Traverse both lists and append the smaller node
  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
  }

  // Append the remaining nodes
  if list1 != nil {
    current.Next = list1
  } else {
    current.Next = list2
  }

  return dummy.Next
}

// Helper function to create a linked list from a slice
func createLinkedList(values []int) *ListNode {
  if len(values) == 0 {
    return nil
  }
  head := &ListNode{Val: values[0]}
  current := head
  for i := 1; i < len(values); i++ {
    current.Next = &ListNode{Val: values[i]}
    current = current.Next
  }
  return head
}

// Helper function to convert linked list to slice for testing
func linkedListToSlice(node *ListNode) []int {
  var result []int
  for node != nil {
    result = append(result, node.Val)
    node = node.Next
  }
  return result
}

func main() {
  list1 := createLinkedList([]int{1, 2, 4})
  list2 := createLinkedList([]int{1, 3, 4})
  result := mergeTwoSortedListsIterative(list1, list2)
  fmt.Println(linkedListToSlice(result))  // [1 1 2 3 4 4]

  list1 = createLinkedList([]int{})
  list2 = createLinkedList([]int{})
  result = mergeTwoSortedListsIterative(list1, list2)
  fmt.Println(linkedListToSlice(result))  // []

  list1 = createLinkedList([]int{})
  list2 = createLinkedList([]int{0})
  result = mergeTwoSortedListsIterative(list1, list2)
  fmt.Println(linkedListToSlice(result))  // [0]
}

Approach 2: Recursive

🎯 Interview Favourite

At each step, decide which of the two next nodes (from list1 or list2) should come first, set it to point to the merged result of the remaining lists, and return it.

This approach is elegant because the problem exhibits optimal substructure: merging two lists is the same as choosing the smaller head and then merging the remainder. The recursion naturally mirrors the structure of linked lists.

Recursion vs Iteration tradeoff

The recursive solution is cleaner conceptually but uses O(m + n) extra space for the call stack. For very long lists, the iterative approach is safer.

⏱ Time O(m + n) Single pass through both lists 💾 Space O(m + n) Call stack depth

Step-by-step Example

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

The recursion tree shows how the problem breaks down:

merge([1, 2, 4], [1, 3, 4])
├─ 1 <= 1 → return 1.next = merge([2, 4], [1, 3, 4])
│  ├─ 2 > 1 → return 1.next = merge([2, 4], [3, 4])
│  │  ├─ 2 < 3 → return 2.next = merge([4], [3, 4])
│  │  │  ├─ 4 > 3 → return 3.next = merge([4], [4])
│  │  │  │  ├─ 4 <= 4 → return 4.next = merge(null, [4])
│  │  │  │  │  └─ return 4
│  │  │  │  └─ result: 4 → 4
│  │  │  └─ result: 3 → 4 → 4
│  │  └─ result: 2 → 3 → 4 → 4
│  └─ result: 1 → 2 → 3 → 4 → 4
└─ result: 1 → 1 → 2 → 3 → 4 → 4

Pseudocode

function mergeTwoSortedListsRecursive(list1, list2):
    // Base cases
    if list1 is null:
        return list2
    if list2 is null:
        return list1

    // Recursive case: choose the smaller head and recurse
    if list1.val <= list2.val:
        list1.next = mergeTwoSortedListsRecursive(list1.next, list2)
        return list1
    else:
        list2.next = mergeTwoSortedListsRecursive(list1, list2.next)
        return list2

Solution Code

Python

merge_two_sorted_lists_recursive.py

from typing import Optional


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


def merge_two_sorted_lists_recursive(
    list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
    """
    Merge two sorted linked lists recursively.

    Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
    Space Complexity: O(m + n) due to the recursion call stack
    """
    # Base cases: if one list is empty, return the other
    if not list1:
        return list2
    if not list2:
        return list1

    # Compare the values and recursively merge
    if list1.val <= list2.val:
        list1.next = merge_two_sorted_lists_recursive(list1.next, list2)
        return list1
    else:
        list2.next = merge_two_sorted_lists_recursive(list1, list2.next)
        return list2


# Helper function to create a linked list from a list
def create_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Helper function to convert linked list to list for easy testing
def linked_list_to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result


# Test cases
list1 = create_linked_list([1, 2, 4])
list2 = create_linked_list([1, 3, 4])
result = merge_two_sorted_lists_recursive(list1, list2)
print(linked_list_to_list(result))  # [1, 1, 2, 3, 4, 4]

list1 = create_linked_list([])
list2 = create_linked_list([])
result = merge_two_sorted_lists_recursive(list1, list2)
print(linked_list_to_list(result))  # []

list1 = create_linked_list([])
list2 = create_linked_list([0])
result = merge_two_sorted_lists_recursive(list1, list2)
print(linked_list_to_list(result))  # [0]

C++

merge_two_sorted_lists_recursive.cpp

#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

/**
 * Merge two sorted linked lists recursively.
 *
 * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
 * Space Complexity: O(m + n) due to the recursion call stack
 */
ListNode* mergeTwoSortedListsRecursive(ListNode* list1, ListNode* list2) {
    // Base cases: if one list is empty, return the other
    if (!list1) {
        return list2;
    }
    if (!list2) {
        return list1;
    }

    // Compare the values and recursively merge
    if (list1->val <= list2->val) {
        list1->next = mergeTwoSortedListsRecursive(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoSortedListsRecursive(list1, list2->next);
        return list2;
    }
}

// Helper function to create a linked list from a vector
ListNode* createLinkedList(const vector<int>& values) {
    if (values.empty()) {
        return nullptr;
    }
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (size_t i = 1; i < values.size(); i++) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// Helper function to print linked list
void printLinkedList(ListNode* node) {
    cout << "[";
    while (node) {
        cout << node->val;
        if (node->next) cout << ", ";
        node = node->next;
    }
    cout << "]" << endl;
}

// Test cases
int main() {
    ListNode* list1 = createLinkedList({1, 2, 4});
    ListNode* list2 = createLinkedList({1, 3, 4});
    ListNode* result = mergeTwoSortedListsRecursive(list1, list2);
    printLinkedList(result);  // [1, 1, 2, 3, 4, 4]

    list1 = createLinkedList({});
    list2 = createLinkedList({});
    result = mergeTwoSortedListsRecursive(list1, list2);
    printLinkedList(result);  // []

    list1 = createLinkedList({});
    list2 = createLinkedList({0});
    result = mergeTwoSortedListsRecursive(list1, list2);
    printLinkedList(result);  // [0]

    return 0;
}

Java

merge_two_sorted_lists_recursive.java

public class merge_two_sorted_lists_recursive {

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * Merge two sorted linked lists recursively.
     *
     * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
     * Space Complexity: O(m + n) due to the recursion call stack
     */
    public static ListNode mergeTwoSortedListsRecursive(ListNode list1, ListNode list2) {
        // Base cases: if one list is empty, return the other
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        // Compare the values and recursively merge
        if (list1.val <= list2.val) {
            list1.next = mergeTwoSortedListsRecursive(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoSortedListsRecursive(list1, list2.next);
            return list2;
        }
    }

    // Helper function to create a linked list from an array
    static ListNode createLinkedList(int[] values) {
        if (values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to print linked list
    static void printLinkedList(ListNode node) {
        System.out.print("[");
        boolean first = true;
        while (node != null) {
            if (!first) System.out.print(", ");
            System.out.print(node.val);
            first = false;
            node = node.next;
        }
        System.out.println("]");
    }

    // Test cases
    public static void main(String[] args) {
        ListNode list1 = createLinkedList(new int[]{1, 2, 4});
        ListNode list2 = createLinkedList(new int[]{1, 3, 4});
        ListNode result = mergeTwoSortedListsRecursive(list1, list2);
        printLinkedList(result);  // [1, 1, 2, 3, 4, 4]

        list1 = createLinkedList(new int[]{});
        list2 = createLinkedList(new int[]{});
        result = mergeTwoSortedListsRecursive(list1, list2);
        printLinkedList(result);  // []

        list1 = createLinkedList(new int[]{});
        list2 = createLinkedList(new int[]{0});
        result = mergeTwoSortedListsRecursive(list1, list2);
        printLinkedList(result);  // [0]
    }
}

JavaScript

merge_two_sorted_lists_recursive.js

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Merge two sorted linked lists recursively.
 *
 * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
 * Space Complexity: O(m + n) due to the recursion call stack
 *
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
function mergeTwoSortedListsRecursive(list1, list2) {
    // Base cases: if one list is empty, return the other
    if (!list1) {
        return list2;
    }
    if (!list2) {
        return list1;
    }

    // Compare the values and recursively merge
    if (list1.val <= list2.val) {
        list1.next = mergeTwoSortedListsRecursive(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoSortedListsRecursive(list1, list2.next);
        return list2;
    }
}

// Helper function to create a linked list from an array
function createLinkedList(values) {
    if (values.length === 0) {
        return null;
    }
    const head = new ListNode(values[0]);
    let current = head;
    for (let i = 1; i < values.length; i++) {
        current.next = new ListNode(values[i]);
        current = current.next;
    }
    return head;
}

// Helper function to convert linked list to array for testing
function linkedListToArray(node) {
    const result = [];
    while (node) {
        result.push(node.val);
        node = node.next;
    }
    return result;
}

// Test cases
let list1 = createLinkedList([1, 2, 4]);
let list2 = createLinkedList([1, 3, 4]);
let result = mergeTwoSortedListsRecursive(list1, list2);
console.log(linkedListToArray(result));  // [1, 1, 2, 3, 4, 4]

list1 = createLinkedList([]);
list2 = createLinkedList([]);
result = mergeTwoSortedListsRecursive(list1, list2);
console.log(linkedListToArray(result));  // []

list1 = createLinkedList([]);
list2 = createLinkedList([0]);
result = mergeTwoSortedListsRecursive(list1, list2);
console.log(linkedListToArray(result));  // [0]

Rust

merge_two_sorted_lists_recursive.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

/**
 * Merge two sorted linked lists recursively.
 *
 * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
 * Space Complexity: O(m + n) due to the recursion call stack
 */
pub fn merge_two_sorted_lists_recursive(
    mut list1: Option<Box<ListNode>>,
    mut list2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    match (list1, list2) {
        (None, _) => list2,
        (_, None) => list1,
        (Some(mut node1), Some(mut node2)) => {
            if node1.val <= node2.val {
                node1.next = merge_two_sorted_lists_recursive(node1.next, Some(node2));
                Some(node1)
            } else {
                node2.next = merge_two_sorted_lists_recursive(Some(node1), node2.next);
                Some(node2)
            }
        }
    }
}

// Helper function to create a linked list from a vector
pub fn create_linked_list(values: Vec<i32>) -> Option<Box<ListNode>> {
    let mut head = None;
    for &val in values.iter().rev() {
        let mut node = Box::new(ListNode::new(val));
        node.next = head;
        head = Some(node);
    }
    head
}

// Helper function to convert linked list to vector for testing
pub fn linked_list_to_vec(mut node: Option<Box<ListNode>>) -> Vec<i32> {
    let mut result = Vec::new();
    while let Some(n) = node {
        result.push(n.val);
        node = n.next;
    }
    result
}

fn main() {
    let list1 = create_linked_list(vec![1, 2, 4]);
    let list2 = create_linked_list(vec![1, 3, 4]);
    let result = merge_two_sorted_lists_recursive(list1, list2);
    println!("{:?}", linked_list_to_vec(result));  // [1, 1, 2, 3, 4, 4]

    let list1 = create_linked_list(vec![]);
    let list2 = create_linked_list(vec![]);
    let result = merge_two_sorted_lists_recursive(list1, list2);
    println!("{:?}", linked_list_to_vec(result));  // []

    let list1 = create_linked_list(vec![]);
    let list2 = create_linked_list(vec![0]);
    let result = merge_two_sorted_lists_recursive(list1, list2);
    println!("{:?}", linked_list_to_vec(result));  // [0]
}

Go

merge_two_sorted_lists_recursive.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

/**
 * Merge two sorted linked lists recursively.
 *
 * Time Complexity: O(m + n) where m and n are the lengths of list1 and list2
 * Space Complexity: O(m + n) due to the recursion call stack
 */
func mergeTwoSortedListsRecursive(list1 *ListNode, list2 *ListNode) *ListNode {
  // Base cases: if one list is empty, return the other
  if list1 == nil {
    return list2
  }
  if list2 == nil {
    return list1
  }

  // Compare the values and recursively merge
  if list1.Val <= list2.Val {
    list1.Next = mergeTwoSortedListsRecursive(list1.Next, list2)
    return list1
  } else {
    list2.Next = mergeTwoSortedListsRecursive(list1, list2.Next)
    return list2
  }
}

// Helper function to create a linked list from a slice
func createLinkedList(values []int) *ListNode {
  if len(values) == 0 {
    return nil
  }
  head := &ListNode{Val: values[0]}
  current := head
  for i := 1; i < len(values); i++ {
    current.Next = &ListNode{Val: values[i]}
    current = current.Next
  }
  return head
}

// Helper function to convert linked list to slice for testing
func linkedListToSlice(node *ListNode) []int {
  var result []int
  for node != nil {
    result = append(result, node.Val)
    node = node.Next
  }
  return result
}

func main() {
  list1 := createLinkedList([]int{1, 2, 4})
  list2 := createLinkedList([]int{1, 3, 4})
  result := mergeTwoSortedListsRecursive(list1, list2)
  fmt.Println(linkedListToSlice(result))  // [1 1 2 3 4 4]

  list1 = createLinkedList([]int{})
  list2 = createLinkedList([]int{})
  result = mergeTwoSortedListsRecursive(list1, list2)
  fmt.Println(linkedListToSlice(result))  // []

  list1 = createLinkedList([]int{})
  list2 = createLinkedList([]int{0})
  result = mergeTwoSortedListsRecursive(list1, list2)
  fmt.Println(linkedListToSlice(result))  // [0]
}

Common mistakes

Watch for these pitfalls

• Creating new nodes instead of reusing: Both input lists’ nodes should be reused in the output. Only the dummy node (if used) should be newly created.
• Forgetting to handle empty lists: If one or both lists are empty, the result should simply be the other list (or null if both are empty).
• Not advancing pointers correctly: Forgetting to move list1 or list2 after attaching a node can cause an infinite loop or incorrect merge.
• Losing reference to the merged list head: Make sure you return the node after the dummy (i.e., dummy.next), not the dummy itself.
• Recursion stack overflow on very long lists: For production code, iterative is safer; for interviews, mention this tradeoff.

Edge cases to handle

Case	Behavior	Example
Both lists empty	Return null	[] + [] → []
First list empty	Return second list	[] + [1, 2] → [1, 2]
Second list empty	Return first list	[1, 2] + [] → [1, 2]
Single-node lists	Merge correctly	[1] + [2] → [1, 2]
Duplicate values	Merge in stable order	[1, 3] + [1, 3] → [1, 1, 3, 3]
Negative values	Treat as regular integers	[-2, 0, 2] + [-1, 1] → [-2, -1, 0, 1, 2]

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

merge_two_sorted_lists_space_optimized.py

"""
Solution for Merge Two Sorted Lists
"""

def solve():
    """Implementation for approach 3 of Merge Two Sorted Lists"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

merge_two_sorted_lists_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Merge Two Sorted Lists
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

MergeTwoSortedListsSpaceOptimized.java

/**
 * Solution for Merge Two Sorted Lists
 * Approach 3
 */
public class MergeTwoSortedListsSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

merge_two_sorted_lists_space_optimized.js

/**
 * Solution for Merge Two Sorted Lists
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

merge_two_sorted_lists_space_optimized.rs

/// Solution for Merge Two Sorted Lists
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

merge_two_sorted_lists_space_optimized.go

package main

import "fmt"

// Solution for Merge Two Sorted Lists
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Merge k Sorted Lists ↗ Hard #23
• Merge Sorted Array ↗ Easy #88
• Sort List ↗ Medium #148
• Add Two Numbers ↗ Medium #2

Interview Tips

Key points to discuss

• Why iterative over recursive? The iterative approach uses O(1) extra space (excluding output) versus O(m + n) for the call stack. For interviews, mention both and discuss the tradeoff.
• Why no new nodes? You are reusing the input nodes’ structure; only the connections change. A dummy node is an exception — it simplifies code by eliminating special cases.
• Why compare and choose? Both lists are sorted, so you only need to compare heads. This greedy choice is optimal.
• Follow-up — Merge k Sorted Lists: Extend this to merge multiple lists using a priority queue or merge pairwise.
• Follow-up — In-place merge of arrays: If you had two sorted arrays, you’d merge in-place from right to left to avoid overwriting unprocessed elements.
• Edge case emphasis: Always check empty list handling in interviews; it is a common mistake and easily caught.

← Previous
#20 Valid Parentheses Next
#22 Generate Parentheses →