21. Merge Two Sorted Lists

1. Description

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

2. Example

Example 1:
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]

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

4. Solutions

My Accepted Solution

n is the sum of nodes in m_l1 and m_l2
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
        ListNode head;
        ListNode *iter = &head;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                iter->next = list1;
                list1 = list1->next;
            } else {
                iter->next = list2;
                list2 = list2->next;
            }

            iter = iter->next;
        }

        iter->next = list1 == nullptr ? list2 : list1;

        return head.next;
    }
};