Saturday, 31 December 2011

Merging of 2 ordered Linked Lists without creating new nodes


#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
 int data;
 struct node *link;
}NODE,*NODEPTR;

NODEPTR insert(NODEPTR start)
{
 NODEPTR temp,cur=start;
 temp=(NODEPTR)malloc(sizeof(NODE));
 if(temp==NULL)
 {
  printf("Memory allocation not possible\n");
  return start;
 }
 printf("Enter the data\n");
 scanf("%d",&temp->data);
 temp->link=NULL;
 if(start==NULL)
  return temp;
 while(cur->link!=NULL)
  cur=cur->link;
 cur->link=temp;
 return start;
}

NODEPTR sl(NODEPTR start1,NODEPTR start2)
{
 NODEPTR start,p,q;
 if(start1==NULL)
  start=start2;
 else if(start2==NULL)
  start=start1;
 else if(start2->data >=start1->data)
  start=start1;
 else
  start=start2;
 p=start1;
 q=start2;
 while(start1!=NULL && start2!=NULL)
 {
  if(start2->data >= start1->data)
  {
   p=p->link;
   if(p!=NULL && p->data < start2->data)
   {
      start1=p;
      continue;
   }
   start1->link=start2;
   start1=p;
  }
  else
  {
   q=q->link;
   if(q!=NULL && q->data < start1->data)
   {
     start2=q;
     continue;
   }
   start2->link=start1;
   start2=q;
  }
 }
 return start;
}

void display(NODEPTR start)
{
 NODEPTR cur=start;
 if(start==NULL)
 {
   printf("List is empty\n");
   return;
 }
 printf("The merged list is \n");
 for(cur=start;cur!=NULL;cur=cur->link)
  printf("%d\t",cur->data);
}

main()
{
 int ch;
 NODEPTR start,start1,start2;
 start=NULL;
 start2=NULL;
 start1=NULL;
 while(1)
 {
  printf("1.Enter into list 1\n2.Enter into list 2\n3.Merge the 2 lists\n4.Display\n");
  scanf("%d",&ch);
  switch(ch)
 {
  case 1 : start1=insert(start1);break;
  case 2 : start2=insert(start2);break;
  case 3 : start=sl(start1,start2);break;
  case 4 : display(start);break;
  default: return;
 }
}
}

No comments:

Post a Comment