Merging of sorted doubly linked list

[ajayk]

why this code giving me an error!

#include<iostream>
#include<assert.h>
using namespace std;
class node
{
public:
node* create(int n);
void Insert(node** head,int n);
void print(node* head);
node* merge(node** head1,node ** head2,node** bar);
private:
node* next;
node* prev;
int data;
};

node* node::create(int n)
{
node* temp=new node;
assert(temp);
temp->data=n;
temp->next=NULL;
temp->prev=NULL;
return temp;
}

void node::Insert(node** head,int n)
{

node* temp=create(n);
if(*head==NULL)
{
*head=temp;
}
else
{
node* foo=(*head);
while(foo->next!=NULL)
{
foo=foo->next;
}
foo->next=temp;
temp->prev=foo;
}
}
node* node::merge(node** head1,node** head2,node** result)
{
//node* foo=NULL;
node* list=*head2;
node* pass=*head1;
if(*head1==NULL)
{
return *head2;
}
else if(*head2==NULL)
{
return *head1;
}
while((*head1)->next!=NULL || (*head2)->next!=NULL)
{
jump:
if((*head1)->data < (*head2)->data){
Insert(result,(*head1)->data);
(*head1)=(*head1)->next;
goto jump;
}

else if((*head1)->data > (*head2)->data){
Insert(result,(*head2)->data);
(*head2)=(*head2)->next;
goto jump;
}
else if((*head1)->data == (*head2)->data){
Insert(result,(*head1)->data);
(*head1)=(*head1)->next;
(*head2)=(*head2)->next;
goto jump;
}

}
return *result;

}
void node::print(node* head)
{
node* temp=head;
if(head==NULL)
{
cout<<"List is Empty!\n";
}
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
int main()
{
node*head1=NULL,*head2=NULL,*res=NULL;
int m,n;
node ni;
cout<<"Enter size of node 1 ?";
cin>>n;
cout<<"Enter node 1 ?\n";
for(int i=0;i<n;++i)
{
cout<<"Enter element ?";
cin>>m;
ni.Insert(&head1,m);
}
cout<<"Enter size of node 2?";
cin>>n;
cout<<"Enter node 2 ?\n";
for(int i=0;i<n;++i)
{
cout<<"Enter element ?";
cin>>m;
ni.Insert(&head2,m);
}
cout<<"Print node 1 : ";
ni.print(head1);
cout<<"Print node 2 : ";
ni.print(head2);
res=ni.merge(&head1,&head2,&res);
ni.print(res);
}

[nuderobmonkey]

At 'node::Insert()' : Is it right that it puts a new node at its tail and not after the '*head' argument?
Also, look at 'node::merge()': Seems the execution could never break out of your goto loop.

[ajayk]

my node::Insert() function puts new node at tail.
the problem is only in node::merge() ,but what it is i don't figure out???

[nuderobmonkey]

Inside your merge() function you are trying to access an element over a pointer pointing to NULL, therefore you get a segmentation fault.

Here a solution how you could solve that:

node* node::merge( node** head1, node** head2, node** result )
{
    if( *head1 == NULL){ return *head2; }
    else if(*head2==NULL) { return *head1; }
    
    do {    
        if ( (*head1)->data < (*head2)->data ){  
            Insert(result,(*head1)->data);
            (*head1)=(*head1)->next;
        }
        else if ( (*head1)->data > (*head2)->data){
            Insert(result,(*head2)->data);
            (*head2)=(*head2)->next;
        }
        else if ( (*head1)->data == (*head2)->data){
            Insert(result,(*head1)->data);
            (*head1)=(*head1)->next;
            (*head2)=(*head2)->next;
        }
   } while ( *head1 != NULL && *head2 != NULL );

   return *result;
}

btw: Why do you pass your args as pointer to pointer to node instead as simple pointer to node, or (easy to handle) references? Also you could make your methods to freestanding functions not belonging to class node.

[ajayk]

Thanks i got it.

node* node::merge( node** head1, node** head2, node** result )
	{
	    if( *head1 == NULL){ return *head2; }
	    else if(*head2==NULL) { return *head1; }

	    do {
	        if ( (*head1)->data < (*head2)->data ){
	            Insert(result,(*head1)->data);
	            (*head1)=(*head1)->next;
	        }
	        else if ( (*head1)->data > (*head2)->data){
	            Insert(result,(*head2)->data);
	            (*head2)=(*head2)->next;
	        }
	        else if ( (*head1)->data == (*head2)->data){
	            Insert(result,(*head1)->data);
	            (*head1)=(*head1)->next;
	            (*head2)=(*head2)->next;
	        }
	   } while ( *head1 != NULL && *head2 != NULL );

	    while((*head1)!=NULL)
	    {
	    	Insert(result,(*head1)->data);
	    	(*head1)=(*head1)->next;
	    }
	    while((*head2)!=NULL)
	    {
	    	Insert(result,(*head2)->data);
	    	(*head2)=(*head2)->next;
	    }
	   return *result;
	}

[nuderobmonkey]

Maybe you need insert both of your nodes if both data values are equal, so that you get all of your nodes:

else if ( (*head1)->data == (*head2)->data){
    Insert(result,(*head1)->data);
    Insert(result,(*head2)->data);
    (*head1)=(*head1)->next;
    (*head2)=(*head2)->next;
}