# 0021. Merge Two Sorted Lists

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0021-merge-two-sorted-lists)

Merge two sorted linked lists and return them as a **sorted** list. The list should be made by **"splicing" together (with) the nodes of the first two lists**.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of nodes in both lists is in the range `[0, 50]`.
* `-100 <= Node.val <= 100`
* Both `l1` and `l2` are sorted in **non-decreasing** order.

```
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: l1 = [], l2 = []
Output: []

Input: l1 = [], l2 = [0]
Output: [0]
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
According to the problem statement, **we cannot create a new linked list** to store sorted nodes.
{% endhint %}

Therefore, **top-down recursion** could help us sort by in-place modification on either l1 or l2 as a starting node.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        #  (base case)
        if not l2 and l1: return l1
        if not l1 and l2: return l2
        if not l1 and not l2: return None
        
        # ==================================================
        #  Linked List + Recursion                         =
        # ==================================================
        # n is the length of l1, and m is the length of l2
        # time  : O(n+m)
        # space : O(n+m)
            
        if l1.val > l2.val: l1, l2 = l2, l1
        l1.next = self.mergeTwoLists(l1.next, l2)
        
        return l1
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n+m)
     * @space : O(n+m)
     */
  
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        /* base case */
        if(l1 != null && l2 == null) return l1;
        if(l1 == null && l2 != null) return l2;
        if(l1 == null && l2 == null) return null;

        if(l2.val < l1.val) {
            ListNode tmp = l1;
            l1 = l2;
            l2 = tmp;
        }
        l1.next = mergeTwoLists(l1.next, l2);
        
        return l1;
    }
}
```

{% endtab %}
{% endtabs %}