21. Merge Two Sorted Lists.cpp

// 21. Merge Two Sorted Lists : https://leetcode.com/problems/merge-two-sorted-lists/

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = nullptr;
        ListNode* current = nullptr;

        if (!list1) {
            return list2;
        }

        if (!list2) {
            return list1;
        }

        if (list1->val <= list2->val) {
            head = list1;
            list1 = list1->next;
        } else {
            head = list2;
            list2 = list2->next;
        }

        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;
        } else {
            current->next = list2;
        }

        return head;
    }
};