Write a function to merge two doubly linked lists The input

Write a function to merge two doubly linked lists. The input lists have their elements in sorted order, from lowest to highest. The output list should also be sorted from lowest to highest. Your algorithm should run in linear time on the length of the output list. Provide an algorithm for your function Implement and show some samples of your miming function

Solution

//merging 2 doubly linked lists

#include<conio.h>
#include<iostream>

//node definition for storing dfferent types of data

struct node
{
int data;
struct node *plink *flink;
};

//execution begins here

void main()
{
struct node *start=NULL,*start1=NULL,*ptr,*temp,*temp1,*ptr1,*ptr2;
int num;
char ch;
clrscr();

//filling details for first list

cout<<“Inserting elements in the first list: “<<endl;
do
{
temp=new node;
cout<<“Enter the element: “;
cin>>num;
temp->data=num;
if(start==NULL)
{
start=temp;
start->plink=NULL;
start->flink=NULL;
}
else
{
temp->flink=start;
temp->plink=NULL;
start->plink=temp;
start=temp;
}
cout<<“Do you want to continue?? “;
cin>>ch;
}while(ch==’y’);
cout<<“Forward traversing of elements: “<<endl;
for(ptr=start;ptr->flink!=NULL;ptr=ptr->flink)
{
cout<<ptr->data<<“\\t”;
}
cout<<ptr->data<<endl;

cout<<“Backward traversing of elements: “<<endl;
for(ptr1=ptr;ptr1!=NULL;ptr1=ptr1->plink)
{
cout<<ptr1->data<<“\\t”;
}
cout<<endl<<“Inserting elements in the second list: “<<endl;
do
{
temp=new node;
cout<<“Enter the element: “;
cin>>num;
temp->data=num;
if(start1==NULL)
{
start1=temp;
start1->plink=NULL;
start1->flink=NULL;
}
else
{
temp->flink=start1;
temp->plink=NULL;
start1->plink=temp;
start1=temp;
}
cout<<“Do you want to continue?? “;
cin>>ch;
}while(ch==’y’);
cout<<“Forward traversing of elements: “<<endl;
for(ptr=start1;ptr->flink!=NULL;ptr=ptr->flink)
{
cout<<ptr->data<<“\\t”;
}
cout<<ptr->data<<endl;
cout<<“Backward traversing of elements: “<<endl;
for(ptr1=ptr;ptr1!=NULL;ptr1=ptr1->plink)
{
cout<<ptr1->data<<“\\t”;
}
//MERGING TWO LISTS
ptr=start;
while(ptr->flink!=NULL)
{
ptr=ptr->flink;
}
ptr->flink=start1;
start1->plink=ptr;
cout<<endl<<“After merging: “<<endl;
cout<<“Forward traversing of list: “<<endl;
for(ptr=start;ptr->flink!=NULL;ptr=ptr->flink)
{
cout<<ptr->data<<“\\t”;
}
cout<<ptr->data<<endl;
cout<<“Backward traversing of list: “<<endl;
for(ptr1=ptr;ptr!=NULL;ptr=ptr->plink)
{
cout<<ptr->data<<“\\t”;
}
getch();
}