21. Merge Two Sorted Lists

Problem

Tags: Linked List, Recursion

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.

Example 1:

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.

Code

C

// 21. Merge Two Sorted Lists (10/8/54149)
// Runtime: 9 ms (12.52%) Memory: 6.11 MB (45.11%) 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists (struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head = (struct ListNode*)calloc(1, sizeof(struct ListNode));
    struct ListNode* tail = head;
    
    while (list1 || list2) {
        if (list2 == NULL) {
            tail->next = list1;
            list1 = list1->next;
        }
        else if (list1 == NULL) {
            tail->next = list2;
            list2 = list2->next;
        }
        else if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        
        tail = tail->next;
    }
    
    return head->next;
}

JS

// 21. Merge Two Sorted Lists (7/14/53737)
// Runtime: 84 ms (54.54%) Memory: 40.37 MB (94.70%) 

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
function mergeTwoLists(l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    let hair = new ListNode();
    let tail = hair;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = l1 || l2;
    return hair.next;
}