Merge two linked lists in C++

In this tutorial, we will learn how to merge two linked lists with algorithm and C++ program.

Merging of two linked lists is the same as the concatenation of two strings. But this time instead of playing with index number we have to play with the address. In this tutorial, we are going to make two linked lists and merging second linked list to first.

How to Merge two linked lists in C++

suppose we have two linked list named as “first” and “second”, first has 1->2->3->4->5 data elements linked with each other in nodes and second has 6->7->8->9->10 data elements linked with each other. since we are merging second into first therefore after merging first will have 1->2->3->4->5->6->7->8->9->7->10 in its data element linked with each other in nodes.

let’s understand the implementation using an algorithm.

Algorithm to combine two linked lists in C++

make the first linked list and insert data in it.
make the second linked list and insert data in it.
start from the top node and find the last node of the first linked list by searching the NULL in the reference (next) of nodes.
save the address of the top node of the second linked list to the reference (next) of the last node of the first linked list

C++ program to merge two linked list

// C++ program to merge two linked list
#include <bits/stdc++.h> 
using namespace std; 
  
// defining a node for link list
class Node  
{  
    public: 
        int data;  
        Node *next;  
};  

void insert(Node **, int);   // Function to insert element in linklist
void Print(Node *);      // function to print a singly linked list 
void merge(Node *, Node **); // // The main function to merge two link 
  
//main function  
int main()  
{  
    Node *first = NULL, *second = NULL;

    //inserting 1, 2 and 3 in first linked list  
    insert(&first, 5);  
    insert(&first, 4);  
    insert(&first, 3); 
    insert(&first, 2);  
    insert(&first, 1);  
    cout<<"First Linked List:\n";  
    Print(first);  
  
    //inserting 4, 5, 6, 7, 8 in secnd linked list
    insert(&second, 10);  
    insert(&second, 9);  
    insert(&second, 8);  
    insert(&second, 7);  
    insert(&second, 6);  
    cout<<"\nSecond Linked List:\n";  
    Print(second);  
  
    merge(first, &second);  
  
    //firstrinting merged linked list
    cout<<"\nMerged list is: ";  
    Print(first);  
  
    return 0;  
}  

// Function to insert element in linklist 
void insert(Node ** head_ref, int new_data)  
{  
    Node* new_node = new Node(); 
    new_node->data = new_data;  
    new_node->next = (*head_ref);  
    (*head_ref) = new_node;  
}  
  
//function to print a singly linked list 
void Print(Node *head)  
{  
    Node *temp = head;  
    while (temp != NULL)  
    {  
        cout<<temp->data<<" ";  
        temp = temp->next;  
    }  
    cout<<endl; 
}  
  
// The main function to merge two link list  
void merge(Node *first, Node **second)  
{  
    Node *firstRef = first;  
  
    // finding the lat node of first linked list  
    while (firstRef->next != NULL)  
    {  
         firstRef = firstRef->next;
    }  
   
    firstRef->next = *second;
}

Output:

First Linked List:
1 2 3 4 5
Second Linked List:
6 7 8 9 10
Merged list is: 1 2 3 4 5 6 7 8 9 10

Time complexity:

O(n) where n is the number of nodes in the first list.

The explanation for merge function:

at line-73 a pointer “firstRef” is declared and initialized with the address of the top node of the first list. This is because instead of using the original top reference variable and missing the top node we have made the same variable that can be used as the top reference variable as “firstRef”.
From line 76 to 79, using firstRef , the last node is found from the first list. This is because we are connecting the second list to the last node of the first list. After getting the last node the address of the first node of the second list is saved to the next of the last node of the first list.

you may also read: