# Merge Two Sorted Lists
**Difficulty:** EASY
[External](https://leetcode.com/problems/merge-two-sorted-lists)
Canonical: https://scaleengineer.com/dsa/problems/merge-two-sorted-lists
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** Linked List
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cognizant](https://scaleengineer.com/companies/cognizant), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Huawei](https://scaleengineer.com/companies/huawei), [Hubspot](https://scaleengineer.com/companies/hubspot), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [Shopee](https://scaleengineer.com/companies/shopee), [Siemens](https://scaleengineer.com/companies/siemens), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [HPE](https://scaleengineer.com/companies/hpe), [Rippling](https://scaleengineer.com/companies/rippling), [Snap](https://scaleengineer.com/companies/snap), [Swiggy](https://scaleengineer.com/companies/swiggy), [Media.net](https://scaleengineer.com/companies/media.net), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Revolut](https://scaleengineer.com/companies/revolut), [Teradata](https://scaleengineer.com/companies/teradata), [Texas Instruments](https://scaleengineer.com/companies/texas-instruments)
---
## Problem
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_.

**Example 1:**

![](https://assets.glich.co/dsa/merge-two-sorted-lists/image0.jpg) 

**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
## Brute Force: Collect, Sort, and Rebuild
This approach involves collecting all the values from both linked lists into an auxiliary data structure like an array, sorting this array, and then constructing a new sorted linked list from the sorted values.
**Time:** O((m+n) log(m+n)) · **Space:** O(m + n)
**Pros:** Simple to conceptualize and implement.; Leverages well-known and optimized built-in sorting algorithms.
**Cons:** Highly inefficient as it does not utilize the pre-sorted nature of the input lists.; Requires extra space proportional to the total number of nodes, which is suboptimal.; Creates an entirely new list of nodes instead of reusing the existing ones.
### Explanation
The core idea is to transform the linked list problem into an array problem, which is often easier to handle. First, we iterate through both `list1` and `list2`, adding each node's value to a list. After collecting all values, we use a standard sorting algorithm (like the one provided by `Collections.sort()` in Java) to sort the list of values in non-decreasing order. Finally, we create a new linked list. We start with a dummy head node to simplify insertion. Then, we iterate through the sorted list of values, creating a new `ListNode` for each value and appending it to our new linked list. The head of this newly created list is then returned.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        java.util.List<Integer> values = new java.util.ArrayList<>();
        ListNode current = list1;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }
        current = list2;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }

        java.util.Collections.sort(values);

        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        for (int val : values) {
            tail.next = new ListNode(val);
            tail = tail.next;
        }

        return dummyHead.next;
    }
}
```
### Algorithm
- 1. Create a list (e.g., `ArrayList`) to store node values.
- 2. Traverse `list1` from head to tail, adding each node's value to the list.
- 3. Traverse `list2` from head to tail, adding each node's value to the list.
- 4. Sort the list of values using a standard sorting algorithm.
- 5. Create a new dummy head `ListNode` to serve as the starting point for the result list.
- 6. Iterate through the sorted values, create a new `ListNode` for each value, and append it to the result list.
- 7. Return the `next` node of the dummy head.

## Recursive Approach
This approach solves the problem recursively. The main idea is that the head of the merged list is the node with the smaller value from the heads of the two input lists. The rest of the merged list is formed by recursively merging the remaining parts of the lists.
**Time:** O(m + n) · **Space:** O(m + n)
**Pros:** The code is often more concise and elegant than the iterative version.; Follows a natural divide-and-conquer pattern which can be easier to reason about.
**Cons:** Can lead to a stack overflow error for very long lists due to deep recursion (though not an issue with the problem's constraints).; The space complexity of O(m+n) due to the recursion stack is not optimal compared to the iterative solution.
### Explanation
The recursion is defined by a function that takes two nodes, `l1` and `l2`, as input and returns the head of the merged list.

**Base Cases:**
- If `l1` is null, it means we have exhausted the first list, so the merged list is simply the rest of `l2`. We return `l2`.
- Similarly, if `l2` is null, we return `l1`.

**Recursive Step:**
- We compare the values of the current heads, `l1.val` and `l2.val`.
- If `l1.val` is smaller or equal, then `l1` is the head of the merged list. The `next` pointer of `l1` should point to the result of merging the rest of `l1` (`l1.next`) with `l2`. We make a recursive call: `l1.next = mergeTwoLists(l1.next, l2)`. Then we return `l1`.
- Otherwise, `l2` is the head. We set `l2.next` to the result of merging `l1` with the rest of `l2` (`l2.next`) via `l2.next = mergeTwoLists(l1, l2.next)`. Then we return `l2`.

This process continues until one of the lists becomes null, at which point the base cases handle the termination.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // Base case: if one list is null, return the other.
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        // Recursive step: compare heads and recurse.
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}
```
### Algorithm
- 1. Define the base cases: If `list1` is null, return `list2`. If `list2` is null, return `list1`.
- 2. Compare the values at the heads of `list1` and `list2`.
- 3. If `list1.val <= list2.val`, the result's head is `list1`. Recursively call the function with `list1.next` and `list2` and assign the result to `list1.next`.
- 4. Return `list1`.
- 5. Otherwise (if `list2.val < list1.val`), the result's head is `list2`. Recursively call the function with `list1` and `list2.next` and assign the result to `list2.next`.
- 6. Return `list2`.

## Iterative Approach with Dummy Head
This is the most optimal approach. It involves iterating through both lists simultaneously and building the merged list by picking the smaller node at each step. A dummy head node is used to simplify the code, avoiding special handling for the first node of the merged list.
**Time:** O(m + n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(m+n).; Optimal space complexity of O(1) (constant space).; Avoids recursion, preventing any potential for stack overflow issues on extremely large inputs.
**Cons:** The code might be slightly more verbose than the recursive version due to manual pointer management.
### Explanation
We start by creating a `dummy` node, which will act as a placeholder for the head of the merged list. We also create a `current` pointer, initialized to this `dummy` node. This `current` pointer will always point to the last node in the merged list we've built so far.

We then iterate as long as both `list1` and `list2` have nodes. In each iteration:
- We compare `list1.val` and `list2.val`.
- If `list1.val` is smaller or equal, we link `current.next` to `list1` and advance `list1` to its next node.
- Otherwise, we link `current.next` to `list2` and advance `list2` to its next node.
- In either case, we move `current` forward to the node we just added (`current = current.next`).

After the loop terminates, one of the lists might still have remaining nodes (since the other one became null). These remaining nodes are already sorted, so we can simply append the non-null list to the end of our merged list.

Finally, the merged list starts at `dummy.next`. We return this node.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // Create a dummy node to serve as the start of the merged list.
        ListNode dummy = new ListNode(-1);
        // Create a pointer to the last node of the merged list.
        ListNode current = dummy;

        // Traverse both lists until one of them is exhausted.
        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 from the non-empty list.
        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }

        // The merged list is the next of the dummy node.
        return dummy.next;
    }
}
```
### Algorithm
- 1. Create a `dummy` node to act as a sentinel head for the result list.
- 2. Create a `current` pointer, initialized to `dummy`.
- 3. Loop while both `list1` and `list2` are not null.
- 4. Inside the loop, compare `list1.val` and `list2.val`.
- 5. If `list1.val <= list2.val`, set `current.next = list1` and advance `list1`.
- 6. Else, set `current.next = list2` and advance `list2`.
- 7. In both cases, advance `current` to `current.next`.
- 8. After the loop, one list may have remaining nodes. Append the non-null list to `current.next`.
- 9. Return `dummy.next`.

# Solutions
### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */ var mergeTwoLists =
  function (list1, list2) {
    const dummy = new ListNode();
    let curr = dummy;
    while (list1 && 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 || list2;
    return dummy.next;
  };

```

### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode MergeTwoLists ( ListNode list1 , ListNode list2 ) { ListNode dummy = new ListNode (); ListNode cur = dummy ; while ( list1 != null && list2 != null ) { if ( list1 . val <= list2 . val ) { cur . next = list1 ; list1 = list1 . next ; } else { cur . next = list2 ; list2 = list2 . next ; } cur = cur . next ; } cur . next = list1 == null ? list2 : list1 ; return dummy . next ; } }
```

### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists ( ListNode list1 , ListNode list2 ) { ListNode dummy = new ListNode (); 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 ? list2 : list1 ; return dummy . next ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: ListNode * mergeTwoLists ( ListNode * list1 , ListNode * list2 ) { ListNode * dummy = new ListNode (); ListNode * curr = dummy ; while ( list1 && 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 ? list1 : list2 ; return dummy -> next ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # without ops after while loop class Solution : def mergeTwoLists ( self , list1 : Optional [ ListNode ], list2 : Optional [ ListNode ]) -> Optional [ ListNode ]: dummy = ListNode () current = dummy while list1 or list2 : v1 = list1 . val if list1 else float ( 'inf' ) v2 = list2 . val if list2 else float ( 'inf' ) if v1 < v2 : current . next = list1 list1 = list1 . next else : current . next = list2 list2 = list2 . next current = current . next return dummy . next ############ # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def mergeTwoLists ( self , list1 : Optional [ ListNode ], list2 : Optional [ ListNode ] ) -> Optional [ ListNode ]: dummy = ListNode () 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 or list2 return dummy . next """ curr.next = list1 or list2 better than: if list1: current.next = list1 if list2: current.next = list2 """ ############ # recursion class ListNode : def __init__ ( self , val = 0 , next = None ): self . val = val self . next = next class Solution : def mergeTwoLists ( self , l1 : ListNode , l2 : ListNode ) -> ListNode : if not l1 : # If l1 is empty, return l2 return l2 if not l2 : # If l2 is empty, return l1 return l1 if l1 . val < l2 . val : l1 . next = self . mergeTwoLists ( l1 . next , l2 ) return l1 else : l2 . next = self . mergeTwoLists ( l1 , l2 . next ) return l2
```