DS (RM) Program - LL - Two Singly Linked Lists to Merge, Append, Union, Intersection

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

typedef struct node
{
   int data;
   struct node *link;
}NODE;
typedef struct {
  int count;
  int *pos;
   NODE *head;
}HEAD;
class linklist
{
 HEAD *pNew;
 public:
 HEAD *createHead()
 {

  pNew = new HEAD;
  if(pNew)
  {
   pNew->head = NULL;
   pNew->count = 0;
   cout<<"Memory allocated\n";
  }
  else
   pNew = NULL;
  return pNew;
 }
 void insertNode(HEAD *pList,int dain)
 {
 int loc,i;
 NODE *pNew,*pPre,*temp;
 pPre =pList->head;

 pNew = new NODE;
 if(pNew == NULL)
  cout<<"\nMemory overflow.\n";
 else
{
  pNew->data = dain;

 }
 temp = pList->head;
 if (dain<temp->data)
 {
  pPre=NULL;
  temp=NULL;
 }
 while (temp!=NULL)
 {
  if(dain>temp->data)
  {
   pPre=temp;
   temp=temp->link;

  }
  else
   temp=temp->link;

 }
 if(pPre==NULL)

 {
  pNew->link = pList->head;
  pList->head =pNew;

  pList->count = pList->count+1;
  cout<<"\ndata is inserted.\n";
 }
 else
 {
   pNew->link = pPre->link;
   pPre->link = pNew;
   pList->count = pList->count+1;
   cout<<"\ndata is inserted.\n";
  }

}
void traverse(HEAD *pList)
{
 NODE *pWalk;
 int i;
 if(pList->head==NULL)
  cout<<"List is empty\n";
 else
 {
pWalk = pList->head;

  i=0;
  cout<<"\n";
  while (i<pList->count)
  {
   cout<<pWalk->data<<"\t";
   pWalk=pWalk->link;
   i++;
  }
  cout<<"\n";
  cout<<"Num ber of elements in linked list is \n"<<pList->count;
 }
}
void appendList(HEAD *pList1, HEAD *pList2)
{
 NODE *pWalk;
 pWalk=pList1->head;
 if(pWalk==NULL)
 {
  cout<<"\n Linked list 1 is empty";
  pList1->head=pList2->head;
  pList1->count=pList2->count;
  traverse(pList1);
 }
 else
 {
  while(pWalk->link!=NULL)
   pWalk=pWalk->link;
  pWalk->link=pList2->head;
  pList1->count=pList1->count + pList2->count;
  traverse(pList1);
 }
}
void mergeList(HEAD *pList1, HEAD *pList2)
{
 int n;
 NODE *pWalk1,*pWalk2,*pNew;
 pWalk1=pList1->head;
 pWalk2=pList2->head;
 cout<<"\nEnter how many nodes to be merged?";
 cin>>n;
 while(pWalk1->link!=NULL)
  pWalk1=pWalk1->link;
 for(int i=0;i<n;i++)
 {
  pNew = new NODE;
  if(pNew == NULL)
cout<<"\nMemory overflow.\n";
  else
   pNew->data = pWalk2->data;
  pNew->link=pWalk1->link;
  pWalk1->link=pNew;
  pWalk1=pWalk1->link;
  pWalk2=pWalk2->link;
       }
       pList1->count =pList1->count+n;
       traverse(pList1);

}
void unionList(HEAD *pList1,HEAD *pList2)
{
 NODE *pWalk1,*pWalk2;
 int f;
 if(pList1->count ==0 && pList2->count==0)
  cout<<"\nBoth lists are empty\n";
 else
 {
 if(pList1->count==0)
 {
  cout<<"\nOutput is:\n";
  traverse(pList2);
 }
 if(pList2->count==0)
 {
  cout<<"\nOutput is:\n";
  traverse(pList1);
 }
 else
 {
  cout<<"\n";
  pWalk1 = pList1->head;
  while (pWalk1!=NULL)
  {
   cout<<pWalk1->data<<"\t";
   pWalk1=pWalk1->link;

  }
  pWalk2=pList2->head;
  while(pWalk2!=NULL)
  {
   pWalk1 = pList1->head;
   while(pWalk1!=NULL)
   {
   if(pWalk2->data==pWalk1->data)
   {
f=0;
    break;
   }
   else
    f=1;

   pWalk1=pWalk1->link;
   }
   if(f==1)
    cout<<pWalk2->data<<"\t";
   pWalk2=pWalk2->link;
  }

 }
     }
}
void intersect(HEAD *pList1,HEAD *pList2)
{
 NODE *pWalk1,*pWalk2;
 int f;
 if(pList1->count==0 ||pList2->count==0)
  cout<<"Intersection is not possible\n";
 else
 {
  pWalk1=pList1->head;
  pWalk2=pList2->head;
  while(pWalk2!=NULL)
  {
   pWalk1=pList1->head;
   while(pWalk1!=NULL)
   {
    if(pWalk1->data==pWalk2->data)
    {
     f=1;
     break;
    }
    else
     f=0;
    pWalk1 = pWalk1->link;
   }
   if(f==1)
    cout<<pWalk2->data<<"\t";
   pWalk2=pWalk2->link;
  }
 }
}
void destroyList(HEAD *pList)
{
NODE *pWalk;
 while (pList->count!=0)
 {
  pWalk=pList->head;
  pList->head = pWalk->link;
  pList->count = pList->count-1;
  free(pWalk);
 }
 free(pList);
 cout<<"Linked list destroyed\n";
}
};
int flag;

void main()
{

 int choice,datain;
 HEAD *pList1, *pList2;
 clrscr();
 linklist l;
 cout<<"\nFor first linked list";
 pList1=l.createHead();
 cout<<"\nFor second linked list";
 pList2=l.createHead();
 while(1)
 {
  cout<<"1. Insert linked list node\n";
  cout<<"2. Insert node into second linked list\n";
  cout<<"3. Traverse linked list1\n";
  cout<<"4. Traverse linked list2\n";
  cout<<"5.Append Lists\n";
  cout<<"6.Merge Lists\n";
  cout<<"7.Print union of two LL\n";
  cout<<"8.Print intersection of two LL\n";
  cout<<"9. Exit\n";
  cout<<"\nEnter choice:";
  cin>>choice;
  switch(choice)
  {


   case 1:
    cout<<"\nEnter the element to be inserted\n";
    cin>>datain;
    l.insertNode(pList1,datain);
   break;
   case 2:
cout<<"\nEnter the element to be inserted\n";
    cin>>datain;
    l.insertNode(pList2,datain);

   break;
   case 3:
    l.traverse(pList1);
   break;
   case 4:
    l.traverse(pList2);
   break;
   case 5:
    l.appendList(pList1,pList2);
   break;
   case 6:
    l.mergeList(pList1,pList2);
   break;
   case 7:
    l.unionList(pList1,pList2);
   break;
   case 8:
    l.intersect(pList1,pList2);
   break;
   case 9:
    l.destroyList(pList1);
    exit(1);
    break;
   default: cout<<"Illegal option\n";
  }
 }
}

Output:

For first linked list
Memory allocated

For second linked list
Memory allocated

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:1

Enter the element to be inserted
12

data is inserted.

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:1

Enter the element to be inserted
15

data is inserted.

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:1

Enter the element to be inserted
18

data is inserted.

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:2

Enter the element to be inserted
12

data is inserted.

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:2

Enter the element to be inserted
16

data is inserted.

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:2

Enter the element to be inserted
20
data is inserted.

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:3

12      15      18
Number of elements in linked list is 3

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:4

12      16      20
Number of elements in linked list is 3

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:5

12      15      18      12      16      20
Number of elements in linked list is 6

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:6

Enter how many nodes to be merged ? : 2

12      15      18      12      16      20      12      16
Number of elements in linked list is 8

1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:7

12      15      18      12      16      20      12      16
1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:8
12      16      20      12      16
1. Insert linked list node
2. Insert node into second linked list
3. Traverse linked list1
4. Traverse linked list2
5.Append Lists
6.Merge Lists
7.Print union of two LL
8.Print intersection of two LL
9. Exit

Enter choice:9

Filed Under: Codes DS2, DS2, Prog DS2 on

DS (RM) Program - LL - Two Singly Linked Lists to Merge, Append, Union, Intersection

Categories

Popular Posts