21. Merge Two Sorted Lists

📝 Problem Details

• Title: 21. Merge Two Sorted Lists
• Link: https://leetcode.com/problems/merge-two-sorted-lists/
• Difficulty: Easy
• Tags/Categories: Linked-List

💭What Were My Initial Thoughts?

- naive approach would be to use a mediating data strucutre 
	- a priority queue for example to maintain order
	- insert elements from priority queue into a new linked list and return the new head
	- we can do this without the use of additional auxillary space
	- only increment one of the lists at a time
		- insert the lower value of the two nodes into the lsit and move its pointer by one
		- if one of the lists compeltes before the 2nd list, append the remaining nodes from the second list to the end of the new list

🤔What Did I Struggle With?

~
need to use a nullptr node as the initial head of the list 
and need to return the next value instead of that dummy nullptr node 

💡 Explanation of Solution

same as intuition

⌛ Complexity Analysis

Time Complexity: O(N)
- iterating through the length of at most 1 lists contents
- as the remaining contents of the larger of the two lists will be inserted directly at the tail of the list

Space Complexity: O(N)
- new list is being constructed of N elements where N is the number of elements in list1 and list2

💻 Implementation of Solution

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode();
        ListNode* curr = dummy;
 
        while(list1 && list2) {
            
            if(list1->val <= list2->val) {
                curr->next = list1;
                list1 = list1->next;
            }
            else {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }
 
        if(!list1) {
            curr->next = list2;
        }
        else {
            curr->next = list1;
        }
 
        return dummy->next;
    }
};