Program : Doubly Linked List – Merging

Program : Doubly Linked List – Merging

// Merging two doubly linked list

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

struct link

{

          int no;

          struct link *next;

          struct link *pre;

};

struct link *node,start,start1,*new1,*local;

void create_link(struct link *node);

void display(struct link *node);

void insert(struct link *node);

void main()

{

          clrscr();

          printf("\n creating doubly linked list");

          node=(struct link *)malloc(sizeof(struct link));

          create_link(node);

          printf("\n First list is as follow\n");

          display(node);

          insert(node);

          printf("\n after merging two list in ascending order : ");

          display(node);

          getch();

}

void create_link(struct link *node)

{

          int i;

          start.next=NULL;

          start.pre=NULL;

          node=&start;

          //printf("%u",node);

          // create first list

          for(i=1;i<=10;i+=2)

          {

                   node->next=(struct link *)malloc(sizeof(struct link));

                   node->next->pre=node;

                   node=node->next;

                   node->no=i;

                   node->next=NULL;

          }

}

void display(struct link *node)

{

          node=start.next;

          while(node)

          {

                   printf("\n  %d",node->no);

                   node=node->next;

          }

}

void insert(struct link *node)

{

   int i;

 

   start1.next=NULL;

   start.pre=NULL;

   new1=&start1;

  // create second list

          for(i=2;i<=10;i+=2)

          {

                   new1->next=(struct link *)malloc(sizeof(struct link));

                   new1->next->pre=new1;

                   new1=new1->next;

                   new1->no=i;

                   new1->next=NULL;

          }

          printf("\n second list is as follow");

       new1=start1.next;

          while(new1)

          {

                   printf("\n  %d",new1->no);

                   new1=new1->next;

          }

          // merging two list

          new1=start1.next;

          while(new1)

           {

              int found=0;

              local=(struct link *)malloc(sizeof(struct link));

              local=new1;

              new1=new1->next;

              node=start.next;

              do

              {

               if(node->no > local->no)

                 {

                     local->next=node;

                     local->pre=node->pre;

                     node->pre->next=local;

                     node->pre=local;

                     found=1;

                     break;

                 }

                 else

                 {

                    node=node->next;

                 }

              }while((node->next) && (!found));

              if(!found)

                {

                     if(node->no > local->no)

                 {

                     local->next=node;

                     local->pre=node->pre;

                     node->pre->next=local;

                     node->pre=local;

                 }

                 else

                 {

                    local->next=NULL;

                    local->pre=node;

                    node->next=local;

                 }

           }

     }

}

Posted  By : Ruchita Pandya