# Merge two sorted Linked Lists

## Algorithm

Time complexity : O(n)

Step 1 : Create a function that takes two sorted linked lists and merge them.
Step 2 : Create a new empty linked list. Till one of the list or both are traversed add elements into the new linked list by comparing the head pointers.
c)     If list1 is traversed completely then just add the remaining list2 at the end of the new list and vice versa.
d)    simply copy the untraversed part of the list as it is already sorted.
Step 3 :  call the function for the given two sorted lists then it gives the final sorted list by merging both the lists.

### Algorithm working Example

Given two linked lists a, b

We need to merge a, b

Step 1 : create a dummy node

Step 2 :  6 < 7 so, add 6

Step 3 :  7 < 8 so, add 7

Step 4 :  8 < 11 so, add 8

Step 5 :  11 < 12 so, add 11

Step 6 :  12 < 14 so, add 7

Step 7 :  Finally add 14, as it is the only 1 left.

## C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LL{
int data;
LL *next;
};

{

{
}

else{

while(temp->next!=NULL)
temp=temp->next;

temp->next=new LL;
temp=temp->next;
temp->data=dataToBeInserted;
temp->next=NULL;
}
//O(number of nodes)
}

{

while(temp1 and temp2) //till one of the list or both lists are traversed
{
if(temp1->data <= temp2->data)
{
insertAtEnd(&finalList,temp1->data);
temp1 = temp1->next;
}
else
{
insertAtEnd(&finalList,temp2->data);
temp2 = temp2->next;
}
}

while(temp1) //simply copy the untraversed part of the list as it is already sorted
{
insertAtEnd(&finalList,temp1->data);
temp1 = temp1->next;
}

while(temp2) //simply copy the untraversed part of the list as it is already sorted
{
insertAtEnd(&finalList,temp2->data);
temp2 = temp2->next;
}

}

{
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

struct LL *head1 = NULL; //initial list has no elements

cout <<"First list is :-\n";

insertAtEnd(&head2,55); //value changed from 15 to 25

cout <<"\nSecond list is :-\n";