Merge Two Sorted Linked List in C++.

Given heads of two sorted Linked lists list1 and list2 arrange in ascending order. Merge the two linked lists into one sorted linked list and return the head of the merged list.

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

Approach 1: Brute Force (Using Iteration). 

Follow the below steps to merge two sorted linked lists:

• 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++ Solution code:

/*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;
}

Output:

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.

Related Articles:

• Convert Binary Linked List to Integer.

• Find the Middle of the Singly Linked List in C++.

• Reverse a Singly Linked List in C++.

• Intersection Point of Two Linked Lists in C++.

• Detect Cycle in a Linked List in C++.