Merge Two Sorted Linked Lists

Problem

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

Merge the two lists into one sorted linked list and return the head of the new sorted linked list.

The new list should be made up of nodes from list1 and list2.

Examples

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,5]

Output: [1,1,2,3,4,5]

Example 2:

Input: list1 = [], list2 = [1,2]

Output: [1,2]

Example 3:

Input: list1 = [], list2 = []

Output: []

Constraints

• 0 <= The length of the each list <= 100.
• -100 <= Node.val <= 100

You should aim for a solution with O(n + m) time and O(1) space, where n is the length of list1 and m is the length of list2.

Solution

Check for empty lists, set head to min of first element and increment that head. Then loop while both lists have payloads, set link, and increment that head. At the end, ensure we check for a leftover list and append to the end.

/**
 * 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* list1, ListNode* list2) {
        // list1 or list2 is empty, return the opposite
        if (!list1) {
            return list2;
        }
        if (!list2) {
            return list1;
        }
 
        // Set head to min first element
        ListNode *head = nullptr;
        if (list1->val < list2->val) {
            head = list1;
            list1 = list1->next;
        } else {
            head = list2;
            list2 = list2->next;
        }
 
        ListNode *current = head;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
 
        if (list1) {
            current->next = list1;
        } 
        if (list2) {
            current->next = list2;
        }
 
        return head;
    }
};