###### tags: `leetcode` `easy` `Linked List` `Recursion`
# [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)

## Description

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

Merge the two lists in a 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
### Example1

**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 \leq Node.val \leq 100$
- Both `list1` and `list2` are sorted in **non-decreasing** order.

## Code

typedef struct ListNode LINODE;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    LINODE ans, *tmp = &ans;
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            tmp->next = list1;
            list1 = list1->next;
        } else {
            tmp->next = list2;
            list2 = list2->next;
        }
        tmp = tmp->next;
    }
    tmp->next = list1 ? list1 : list2;
    return ans.next;
}

## Complexity

|Space |Time |
|- |- |
|$O(1)$|$O(Min(list1, list2))$|

## Result

- Runtime : 0 ms, 100%
- Memory usage : 6.2 MB, 27.97%