21 Merge Two Sorted Lists

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

• With my approach, I just began a new linked list and used two different pointers to iterate through both elements while keeping track of the smallest one.

• My alg. uses O(1) space and O(N) time complexity, which is the best you can get, although the code could potentially be cleaner.

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    else if (!l2) return l1;

    // check which end is greater
    ListNode *newNode = nullptr;
    ListNode *newNodeIter = nullptr;
    ListNode *iter1 = l1, *iter2 = l2;
    ListNode *prev1 = nullptr, *prev2 = nullptr;

    // start us off
    if (l1->val < l2->val) {
        newNode= l1;
        prev1 = iter1;
        iter1 = iter1->next;
    }
    else {
        newNode= l2;
        prev2 = iter2;
        iter2 = iter2->next;
    }

    newNodeIter = newNode;

    while (iter1 && iter2) {
        if (iter1->val < iter2->val) {
            newNodeIter->next = iter1;
            newNodeIter = iter1;
            prev1 = iter1;
            iter1 = iter1->next;
        }
        else {
            newNodeIter->next = iter2;
            newNodeIter = iter2;
            prev2 = iter2;
            iter2 = iter2->next;
        }
    }
    // at this point either same size, or one is larger 
    if (!iter1 && iter2) {
        // iter2 has large vals
        prev1->next = iter2;
    }
    else if (iter1 && !iter2) {
        prev2->next = iter1;
    }
    // else the same size
    return newNode;


}