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

```cpp
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;


}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/21_merge_two_sorted_lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.