Skip to main content
CodePeetCodePeet
CodePeet 150

Merge Two Sorted Lists

EASYProblemSolveExternal Links

Description

You are given the heads of two sorted linked lists, list1 and list2. Each list has its nodes arranged in non-decreasing order.

Your task is to merge these two lists into a single sorted linked list. The merged list should be constructed by rearranging (splicing together) the nodes from the original two lists — not by creating new nodes.

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]

Explanation: We compare nodes from both lists and always pick the smaller one. Starting with 1 from list1 and 1 from list2 (both equal, pick either), then 2 from list1, then 3 from list2, then both 4s. The merged result preserves sorted order throughout.

Example 2

Input: list1 = [], list2 = []

Output: []

Explanation: Both lists are empty. There are no nodes to merge, so the result is also an empty list.

Example 3

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

Output: [0]

Explanation: One list is empty and the other has a single node with value 0. The merged result is simply the non-empty 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

Editorial

Brute Force

Intuition

The simplest way to think about merging two sorted lists is to forget about the linked list structure entirely. Imagine you have two stacks of sorted playing cards and you want one combined sorted stack. The easiest (though not most efficient) approach: dump all the cards into one pile, sort the whole pile, and then arrange them back into a line.

Translated to code: collect all node values from both linked lists into an array, sort that array, and then build a brand-new linked list from the sorted values. This approach doesn't take advantage of the fact that both input lists are already sorted — it treats them as if they were unsorted collections.

Step-by-Step Explanation

Let's trace through with list1 = [1, 2, 4], list2 = [1, 3, 4]:

Step 1: Initialize an empty array to collect all values.

  • arr = []

Step 2: Traverse list1 and collect all values.

  • Visit node 1 → arr = [1]
  • Visit node 2 → arr = [1, 2]
  • Visit node 4 → arr = [1, 2, 4]

Step 3: Traverse list2 and collect all values.

  • Visit node 1 → arr = [1, 2, 4, 1]
  • Visit node 3 → arr = [1, 2, 4, 1, 3]
  • Visit node 4 → arr = [1, 2, 4, 1, 3, 4]

Step 4: Sort the combined array.

  • arr = [1, 1, 2, 3, 4, 4]

Step 5: Build a new linked list from the sorted array.

  • Create node 1 → node 1 → node 2 → node 3 → node 4 → node 4

Step 6: Return the head of the new list: [1, 1, 2, 3, 4, 4].

Brute Force — Collect, Sort, Rebuild — Watch how we gather all node values into an array, sort them, and observe the sorted result that will become our new linked list.

Algorithm

  1. Create an empty array
  2. Traverse list1, appending each node's value to the array
  3. Traverse list2, appending each node's value to the array
  4. Sort the combined array
  5. Create a new linked list from the sorted array values
  6. Return the head of the new linked list

Code

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        vector<int> arr;
        
        ListNode* curr = list1;
        while (curr != nullptr) {
            arr.push_back(curr->val);
            curr = curr->next;
        }
        
        curr = list2;
        while (curr != nullptr) {
            arr.push_back(curr->val);
            curr = curr->next;
        }
        
        sort(arr.begin(), arr.end());
        
        ListNode* dummy = new ListNode(-1);
        curr = dummy;
        for (int val : arr) {
            curr->next = new ListNode(val);
            curr = curr->next;
        }
        
        return dummy->next;
    }
};
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        arr = []
        
        curr = list1
        while curr:
            arr.append(curr.val)
            curr = curr.next
        
        curr = list2
        while curr:
            arr.append(curr.val)
            curr = curr.next
        
        arr.sort()
        
        dummy = ListNode(-1)
        curr = dummy
        for val in arr:
            curr.next = ListNode(val)
            curr = curr.next
        
        return dummy.next
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        List<Integer> arr = new ArrayList<>();
        
        ListNode curr = list1;
        while (curr != null) {
            arr.add(curr.val);
            curr = curr.next;
        }
        
        curr = list2;
        while (curr != null) {
            arr.add(curr.val);
            curr = curr.next;
        }
        
        Collections.sort(arr);
        
        ListNode dummy = new ListNode(-1);
        curr = dummy;
        for (int val : arr) {
            curr.next = new ListNode(val);
            curr = curr.next;
        }
        
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O((n + m) × log(n + m))

We traverse both lists in O(n + m) to collect values. Sorting the combined array of (n + m) elements takes O((n + m) × log(n + m)). Building the result list takes O(n + m). The sorting step dominates, giving us O((n + m) × log(n + m)) overall.

Space Complexity: O(n + m)

We store all (n + m) node values in an auxiliary array, and we create (n + m) new nodes for the result list. Both require O(n + m) extra space.

Why This Approach Is Not Efficient

The brute force approach completely ignores the most valuable property of our input: both lists are already sorted. By dumping everything into an array and re-sorting, we are doing O((n + m) log(n + m)) work when a linear O(n + m) merge is possible.

Think about it this way: if someone hands you two pre-sorted stacks of exams (sorted by student name), would you shuffle them together randomly and then re-sort the whole pile? Of course not — you would compare the top exam from each stack and pick the one that comes first alphabetically, building a merged pile one exam at a time. That merge operation takes only one pass through both stacks.

Additionally, the brute force creates entirely new nodes instead of reusing the existing ones, wasting O(n + m) extra space unnecessarily.

Key insight for improvement: Since both lists are sorted, we can merge them in a single pass by always choosing the smaller of the two current heads — much like the merge step of merge sort.

Better Approach - Recursive Merge

Intuition

Since both lists are sorted, at every step we only need to decide one thing: which list's current head is smaller? Whichever is smaller becomes the next node in our merged list, and then we recursively merge the remainder.

Imagine two friends reading off numbers from their sorted lists. At each moment, the friend with the smaller number speaks first. That number joins the merged sequence, and that friend moves to their next number. The process repeats until one friend runs out — at which point the other friend reads off all their remaining numbers.

Recursion captures this beautifully: compare the two heads, pick the smaller one, attach it to the result of merging the rest, and let the recursion handle everything else.

Step-by-Step Explanation

Let's trace with list1 = [1, 2, 4], list2 = [1, 3, 4]:

Step 1: Compare heads: list1.val = 1, list2.val = 1. They're equal, so pick list1's head (1). Recurse with list1 = [2, 4], list2 = [1, 3, 4].

Step 2: Compare heads: list1.val = 2, list2.val = 1. list2 is smaller (1 < 2), so pick list2's head (1). Recurse with list1 = [2, 4], list2 = [3, 4].

Step 3: Compare heads: list1.val = 2, list2.val = 3. list1 is smaller (2 < 3), so pick list1's head (2). Recurse with list1 = [4], list2 = [3, 4].

Step 4: Compare heads: list1.val = 4, list2.val = 3. list2 is smaller (3 < 4), so pick list2's head (3). Recurse with list1 = [4], list2 = [4].

Step 5: Compare heads: list1.val = 4, list2.val = 4. Equal, pick list1's head (4). Recurse with list1 = [], list2 = [4].

Step 6: list1 is empty (null). Base case reached — return list2 = [4].

Unwinding: The recursion links everything together: 1 → 1 → 2 → 3 → 4 → 4.

Recursive Merge — Choosing the Smaller Head at Each Level — At each recursive call, we compare the two list heads, pick the smaller one, and let recursion handle the remaining nodes. Watch the merged list grow as the recursion unwinds.

Algorithm

  1. Base cases: If list1 is null, return list2. If list2 is null, return list1.
  2. Compare heads: Look at the values of the current heads of both lists.
  3. Pick the smaller head:
    • If list1.val ≤ list2.val, pick list1's head. Set list1.next = recursiveMerge(list1.next, list2). Return list1.
    • Otherwise, pick list2's head. Set list2.next = recursiveMerge(list1, list2.next). Return list2.
  4. The recursion naturally builds the merged list as it unwinds.

Code

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;
        }
    }
};
class Solution:
    def mergeTwoLists(self, 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 = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2
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;
        }
    }
}

Complexity Analysis

Time Complexity: O(n + m)

Each recursive call processes exactly one node (either from list1 or list2). Since there are n + m total nodes, we make at most n + m recursive calls. Each call does O(1) work (a comparison and a pointer reassignment), so the total time is O(n + m).

Space Complexity: O(n + m)

Each recursive call adds a frame to the call stack. In the worst case, we recurse n + m times (one call per node), so the call stack uses O(n + m) space. This is the key drawback compared to an iterative approach.

Why This Approach Is Not Efficient

The recursive approach achieves optimal O(n + m) time complexity, which is a significant improvement over the brute force's O((n + m) log(n + m)). However, it has a critical space inefficiency: O(n + m) stack space due to recursion.

Every recursive call consumes memory on the call stack. With n + m total nodes, the recursion can go n + m levels deep. For very long lists, this can cause a stack overflow — a runtime crash when the program runs out of stack memory.

The question becomes: can we achieve the same O(n + m) time complexity while using only O(1) extra space? Yes — by converting the recursive logic into an iterative loop with a dummy head node, we eliminate the call stack overhead entirely.

Optimal Approach - Iterative Merge with Dummy Node

Intuition

The iterative approach works exactly like the recursive one conceptually — at each step, compare the two current heads and attach the smaller one to our result — but it uses a loop instead of recursion, eliminating the stack overhead.

The key trick is using a dummy node: a placeholder node at the start of our result list. This avoids special-case logic for initializing the merged list's head. We maintain a current pointer that always points to the last node of our merged list, and we keep appending the smaller of the two heads.

Picture two queues of people sorted by height. You stand at a new empty line (the dummy), and you repeatedly compare the front person from each queue. The shorter one steps into your new line. When one queue empties, everyone remaining in the other queue walks over to join the end of your line.

Step-by-Step Explanation

Let's trace with list1 = [1, 2, 4], list2 = [1, 3, 4]:

Step 1: Create a dummy node. Set current = dummy. list1 points to node 1, list2 points to node 1.

Step 2: Compare list1.val (1) vs list2.val (1). 1 ≤ 1, so attach list1's node (1) to current.next. Advance list1 to its next node (2). Move current forward.

  • Merged so far: dummy → 1

Step 3: Compare list1.val (2) vs list2.val (1). 1 < 2, so attach list2's node (1) to current.next. Advance list2 to its next node (3). Move current forward.

  • Merged so far: dummy → 1 → 1

Step 4: Compare list1.val (2) vs list2.val (3). 2 < 3, so attach list1's node (2). Advance list1 to node 4. Move current forward.

  • Merged so far: dummy → 1 → 1 → 2

Step 5: Compare list1.val (4) vs list2.val (3). 3 < 4, so attach list2's node (3). Advance list2 to node 4. Move current forward.

  • Merged so far: dummy → 1 → 1 → 2 → 3

Step 6: Compare list1.val (4) vs list2.val (4). 4 ≤ 4, so attach list1's node (4). Advance list1 to null. Move current forward.

  • Merged so far: dummy → 1 → 1 → 2 → 3 → 4

Step 7: list1 is null. Loop ends. Attach remaining list2 (node 4) to current.next.

  • Merged: dummy → 1 → 1 → 2 → 3 → 4 → 4

Step 8: Return dummy.next, which is the head of [1, 1, 2, 3, 4, 4].

Iterative Merge — Building the Result with a Dummy Node — Watch the current pointer build the merged list node by node. At each step, the smaller head is detached from its original list and attached to the growing result.

Algorithm

  1. Create a dummy node to serve as the starting point of the merged list
  2. Initialize a current pointer pointing to dummy
  3. While both list1 and list2 are non-null:
    • Compare list1.val and list2.val
    • If list1.val ≤ list2.val, set current.next = list1, advance list1 = list1.next
    • Otherwise, set current.next = list2, advance list2 = list2.next
    • Advance current = current.next
  4. After the loop: One list may still have remaining nodes. Set current.next to whichever list is non-null (list1 or list2)
  5. Return dummy.next (the actual head of the merged list)

Code

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(-1);
        ListNode* curr = &dummy;
        
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                curr->next = list1;
                list1 = list1->next;
            } else {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }
        
        curr->next = (list1 != nullptr) ? list1 : list2;
        
        return dummy.next;
    }
};
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        curr = dummy
        
        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next
        
        curr.next = list1 if list1 else list2
        
        return dummy.next
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
        
        curr.next = (list1 != null) ? list1 : list2;
        
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(n + m)

Each iteration of the while loop processes exactly one node from either list1 or list2 and appends it to the merged list. After the loop, any remaining nodes from the non-empty list are attached in O(1). Since there are n + m total nodes, the loop runs at most n + m times. Each iteration performs O(1) work (one comparison, one pointer update), giving O(n + m) total.

Space Complexity: O(1)

We only use a constant amount of extra space: the dummy node and the current pointer. Unlike the recursive approach, there is no call stack overhead. Unlike the brute force, there is no auxiliary array. We reuse the existing nodes from both lists by simply re-pointing their next pointers, so no new nodes are created.