> For the complete documentation index, see [llms.txt](https://anton-veselskyi.gitbook.io/codding-problems-solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/easy/merge-two-sorted-lists.md).

# Merge Two Sorted Lists

## [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists)

Merge two sorted linked lists and return it as a **sorted** list. The list should be made by splicing together the nodes of the first two lists.

**Example 1:** ![](https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg)

```

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

**Example 2:**

```

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

**Example 3:**

```

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

**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.

## Solutions

### 🧠 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* l1, ListNode* l2)
    {
        //input validation
        if(!l1 && !l2)
            return nullptr;
        if(!l1)
            return l2;
        if(!l2)
            return l1;

        //init of vars
        ListNode *&min_val_node = l1->val < l2->val ? l1 : l2;
        const int start_val = min_val_node->val;
        min_val_node = min_val_node->next;

        ListNode *new_list_start = new ListNode(start_val),
                 *new_list_iter = new_list_start;

        //O(n) solution, two pointers
        //while we have somthing in lists - merge them
        while(l1 || l2)
        {
            if(l2 == nullptr || (l1 && l1->val < l2->val)) 
            {
                new_list_iter->next = new ListNode(l1->val);
                new_list_iter = new_list_iter->next;
                l1 = l1->next;
            }
            else
            {
                new_list_iter->next = new ListNode(l2->val);
                new_list_iter = new_list_iter->next;
                l2 = l2->next;
            }
        }

        return new_list_start;
    }
};
```