tags: leetcode easy Linked List Recursion

21. 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%