Merge Sorted Linked List -Leetcode-Amazon Interview Question

Problem description can be found here:

Prerequisites :

1. Problem solving attitude and you must know what you are doing !
2. Pointers, Linked List

When it comes to solving Linked List problems you have to set up your mind to follow the pointers strictly, otherwise pointers are very smart in deceiving you if you happen to deviate your attention for a bit !

When working with pointers, you are allowed to use whiteboard to visualize the tracking of pointers!

But, sorry I cannot let you use white board for recursion! my post, my rule 😉To make a sense of what I am talking about check my previous post.

Let us code it up !

Create a “head” pointer and assign it a first correct node ,i.e the first smallest valued node of the given 2 lists. Then, assign the second smallest valued node of 2 lists to the “next” pointer of the “head” node.Repeat this process of assigning “next” pointer of current node with next node that has the bigger node value than the current one until no more nodes are left to assign. You will need another temporary pointer variable that points to the nodes as they are being linked because head pointer has to be fixed once it is set as it is the starting point of the linked list. Finally, return “head” pointer at the end of the function. “head” pointer will allow you to access all the elements in the linked list by following the “next” pointer until no more nodes left!

My solution’s runtime beats 97.3% of cpp submissions and the memory usage beats 74% of cpp submissions!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
        if(!l1 && !l2){
            return NULL;
        }
        else if(l1 && !l2){
            return l1;
        }
        else if(!l1 && l2){
            return l2;
        }
       
        ListNode * temp1 = l1; 
        ListNode * temp2 = l2;
        ListNode * temp3 = NULL;
        ListNode * head = NULL;
        
        while(temp1 && temp2){
            
            if(temp1->val <= temp2->val){
                //initialize head if it is NULL
                if(head == NULL){
                    head = temp1;
                    temp3 = head;
                    temp1 = temp1->next;
                }
                else{
                    temp3->next = temp1;
                    temp3 = temp3->next; 
                    temp1 = temp1->next;
                }
            }
            //list 1 value is greater than list2 value
            else{
                //initialize head if it is NULL
                if(head == NULL){
                    head = temp2;
                    temp3 = head;
                    temp2 = temp2->next;
                }
                else{
                    temp3->next = temp2;
                    temp3 = temp3->next; 
                    temp2 = temp2->next;
                }
                
            }
        } //end of while 
        //if list1 still has elements
        while(temp1){
            temp3->next = temp1;
            temp3= temp3->next;
            temp1 = temp1->next; 
        }
        //if list2 still has elements 
        while(temp2){
            temp3->next = temp2;
            temp3= temp3->next;
            temp2 = temp2->next;     
        }
       
        return head; 
        
    }
};