Merge two sorted Linked List

Problem Statement .

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

**Example test Case **

INPUT: list1 = [1,2,4], list2 = [1,3,4] OUTPUT: [1,1,2,3,4,4]

Solution with Dummy Node(Using O(N) Space)

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

Optimal Solution :

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    
    if(NULL == l1) return l2;
    if(NULL == l2) return l1;
    
    ListNode* head=NULL;    // head of the list to return
    
    // find first element (can use dummy node to put this part inside of the loop)
    if(l1->val < l2->val)       { head = l1; l1 = l1->next; }
    else                        { head = l2; l2 = l2->next; }
    
    ListNode* p = head;     // pointer to form new list
    
    // I use && to remove extra IF from the loop
    while(l1 && l2){
        if(l1->val < l2->val)   { p->next = l1; l1 = l1->next; }
        else                    { p->next = l2; l2 = l2->next; }
        p=p->next;
    }
    
    // add the rest of the tail, done!
    if(l1)  p->next=l1;
    else    p->next=l2;
    
    return head;
}

Reference or to practice the problem link https://leetcode.com/problems/merge-two-sorted-lists/