Merge Two Sorted Linked List in C++.

Example 1: 
Input: 

list1: 1->2->3->4->NULL

list2: 1->3->5->NULL
Output: 1->1->2->3->3->4->5->NULL

Example 2:
Input: 

list1: 1->NULL
list2: 
Output: 1->NULL

• If list1 is NULL then simply return the head of list2 and if list2 is NULL then simply return the head of list1.
• Declare a temp pointer that will point to a list containing the smaller value in the head node.
• One traverses the lists until one of them gets exhausted, chooses a smaller current node and links it with the tail of the merged list and then moves the current pointer of that list one step forward.
• If you reach a condition in which one of the lists got exhausted then simply link the remaining list to the tail of the merged list.

/*C++ Program to Merge Sorted Linked List*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to merge sorted linked lists
ListNode *mergeList(ListNode *list1, ListNode *list2){

    if(list1 == NULL ) return list2;
    if(list2 == NULL ) return list2;

    ListNode *ptr;
    if(list1->data > list2->data){
        ptr = list2;
        list2 = list2->next;
    }
    else{
        ptr = list1;
        list1 = list1->next;
    }

    ListNode *curr = ptr;

    while(list1 != NULL && list2 != NULL){

        if(list1->data < list2->data){
            curr->next = list1;
            list1 = list1->next;
        }
        else{
            curr->next = list2;
            list2 = list2->next;
        }
        curr = curr->next;
    }
    if(list1 != NULL){
        curr->next = list1;
    }
    else{
        curr->next = list2;
    }
    return ptr;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
int main(){
    //sorted list 1
    ListNode *list1 = newNode(1);
    list1->next = newNode(2);
    list1->next->next = newNode(3);
    list1->next->next->next = newNode(4);
    //sorted list 2
    ListNode *list2 = newNode(1);
    list2->next = newNode(3);
    list2->next->next = newNode(5);

    ListNode *merge = NULL;

    cout<<"Linked List1: ";
    printList(list1);

    cout<<"\nLinked List2: ";
    printList(list2);

    merge = mergeList(list1, list2);

    cout<<"\nSorted Linked List after merge: ";
    printList(merge);
    return 0;
}

Linked List1: 1 2 3 4
Linked List2: 1 3 5
Sorted Linked List after merge: 1 1 2 3 3 4 5

• Time Complexity: O(n) where n is the total number of nodes by adding list1 and list2.
• Space Complexity: O(1) no extra space is required.