Merge Two Sorted Lists

easy
Linked ListLinked ListRecursion

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

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

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]

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.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Iterative

Intuition

We use a dummy head node to simplify the merging logic, then compare the heads of both lists one step at a time. At each step, we attach the smaller node to our result list and advance that list's pointer. This is similar to the merge step in merge sort. The dummy node avoids special-casing the head of the result list -- at the end, we simply return dummy.next. After one list is exhausted, we attach the remainder of the other list directly since it is already sorted.

Algorithm

  1. Create a dummy node to serve as the head of the merged list. Initialize a 'current' pointer to the dummy node.
  2. While both list1 and list2 are non-null, compare their values.
  3. Attach the node with the smaller value to current.next and advance that list's pointer.
  4. Advance the current pointer to current.next.
  5. When the loop ends, one list may still have remaining nodes. Attach it to current.next.
  6. Return dummy.next as the head of the merged list.
TimeO(n + m)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(-1);
        ListNode* current = &dummy;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }

        current->next = (list1 != nullptr) ? list1 : list2;

        return dummy.next;
    }
};
Java 21
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        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;
        }

        current.next = (list1 != null) ? list1 : list2;

        return dummy.next;
    }
}
Python 3.12
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(-1)
    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
Go 1.26
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    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
    }
    if list1 != nil {
        current.Next = list1
    } else {
        current.Next = list2
    }
    return dummy.Next
}
Approach 2

Recursive

Intuition

The recursive approach leverages the observation that merging two sorted lists can be defined recursively: the merged list starts with the smaller of the two heads, followed by the merge of the remaining elements. The base case is when one list is empty, in which case we return the other list. This approach is elegant and concise but uses O(n + m) stack space due to recursion depth, which can be a concern for very long lists.

Algorithm

  1. Base case: if list1 is null, return list2. If list2 is null, return list1.
  2. Compare the values of the two head nodes.
  3. If list1.val <= list2.val, set list1.next to the result of recursively merging list1.next with list2. Return list1.
  4. Otherwise, set list2.next to the result of recursively merging list1 with list2.next. Return list2.
TimeO(n + m)SpaceO(n + m)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;

        if (list1->val <= list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};
Java 21
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}
Python 3.12
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    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
Go 1.26
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }
    if list2 == nil {
        return list1
    }
    if list1.Val <= list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    }
    list2.Next = mergeTwoLists(list1, list2.Next)
    return list2
}

Frequently asked questions

What is the optimal time complexity of Merge Two Sorted Lists?

The most efficient approach in this guide ("Recursive") runs in O(n + m) time and uses O(n + m) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Merge Two Sorted Lists use?

Merge Two Sorted Lists is a easy-level Linked List problem involving Linked List, Recursion. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Merge Two Sorted Lists be solved without extra space?

The most space-efficient approach in this guide uses O(n + m) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(n + m).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
list1=
[1,2,4]
list2=
[1,3,4]
Expected Output
[1,1,2,3,4,4]