Tuesday, 14 February 2017

C++ Program for merging two sorted Linked List (Recursive Solution)

This question has been already appeared in the interviews of following companies:-
 Amazon, Microsoft, Oracle, Brocade, Factset, Flipkart, Belzabar, Samsung, Synopsys, OATS Systems.

Source:  geeksforgeeks

The exact question was like this:-

Given two linked lists sorted in ascending order. Merge them in-place and return head of the merged list. For example, if first list is 10->20->30 and second list is 15->17, then the result list should be 10->15->17->20->30.

 It is strongly recommended to do merging in-place using O(1) extra space.

In this question, we just have to create a function which merge both Linked List in just O(1) space and return head of the merged Linked List. The exact code to this question is:

node* linklist::sorted_merge(struct node *currentA,struct node *currentB)
{
 if(currentA==NULL && currentB==NULL)
 {
  return NULL;
 }
 if(currentA!=NULL && currentB==NULL)
 {
  return currentA;
 }
 if(currentA==NULL && currentB!=NULL)
 {
  return currentB;
 }
 if(currentA->data<currentB->data)
 {
  currentA->next=sorted_merge(currentA->next,currentB);
 }
 else
 {
  temp=currentB;
  currentB=currentB->next;
  temp->next=currentA;
  currentA=temp;
  currentA->next=sorted_merge(currentA->next,currentB);
 }
 return currentA;
}



Complete program:

#include <stdio.h>
#include <stdlib.h>
struct node
{
 int data;
 struct node *next;
};
class linklist
{
 private:
     node *headA=NULL;
     node *headB=NULL;
     node *temp;
 public:
     void create(int ch);
     void print(int ch);
     int check();
     node* sorted_merge(struct node *headA,struct node *headB);
     
};
void linklist::create(int ch)
{
 switch(ch)
 {
  case 1: temp=(struct node*)malloc(sizeof(struct node));
          temp->data=10;
          temp->next=NULL;
          headA=temp;
          temp->next=(struct node*)malloc(sizeof(struct node));
          temp=temp->next;
          temp->data=20;
          temp->next=(struct node*)malloc(sizeof(struct node));
          temp=temp->next;
          temp->data=30;
          temp->next=NULL;
          break;
  case 2: temp=(struct node*)malloc(sizeof(struct node));
          temp->data=15;
          headB=temp;
          temp->next=(struct node*)malloc(sizeof(struct node));
          temp=temp->next;
          temp->data=17;
          temp->next=NULL;
          break;
  default: printf("\nError, something went wrong");
 }
}
void linklist::print(int ch)
{
 switch(ch)
 {
  case 1: temp=headA;
          printf("\n");
          while(temp!=NULL)
          {
           printf("%d->",temp->data);
           temp=temp->next;
          }
          break;

     case 2: temp=headB;
             printf("\n");
             while(temp!=NULL)
             {
              printf("%d->",temp->data);
              temp=temp->next;
             }
             break;

     case 3: temp=headA;
             printf("\n");
             while(temp!=NULL)
             {
              printf("%d->",temp->data);
              temp=temp->next;
             }
             break;
     default: printf("\n Error, something went wrong");
 }

}
int linklist::check()
{
 if(headA->data<headB->data)
 {
  headA=sorted_merge(headA,headB);
 }
 else
 {
  headA=sorted_merge(headB,headA);
 }
}
node* linklist::sorted_merge(struct node *headA,struct node *headB)
{
 if(headA==NULL && headB==NULL)
 {
  return NULL;
 }
 if(headA!=NULL && headB==NULL)
 {
  return headA;
 }
 if(headA==NULL && headB!=NULL)
 {
  return headB;
 }
 if(headA->data<headB->data)
 {
  headA->next=sorted_merge(headA->next,headB);
 }
 else
 {
  temp=headB;
     headB=headB->next;
  temp->next=headA;
  headA=temp;
  headA->next=sorted_merge(headA->next,headB);
 }
 return headA;
}
int main()
{
 linklist ll;
 ll.create(1);
 ll.create(2);
 ll.print(1);
 ll.print(2);
 ll.check();
 ll.print(3);
 
 return 0;
}


OUTPUT:


 
If you want to take input from the user to create first two Linked List then replace the whole create() function with the code given below

void linklist::create(int ch)
{
 int item,cont;
 switch(ch)
 {
  case 1: do
          {
           printf("\nEnter the value to insert in list 1: ");
           scanf("%d",&item);
           if(headA==NULL)
           {
                        temp=(struct node*)malloc(sizeof(struct node));
               temp->data=item;
               temp->next=NULL;
               headA=temp;
           }
           else
           {
            temp->next=(struct node*)malloc(sizeof(struct node));
            temp=temp->next;
            temp->data=item;
            temp->next=NULL;
           }
           printf("\nDo you want to continue[1/0]: ");
           scanf("%d",&cont);
          }while(cont==1);
          break;


  case 2: do
          {
           printf("\nEnter the value to insert in list 2: ");
           scanf("%d",&item);
           if(headB==NULL)
           {
                        temp=(struct node*)malloc(sizeof(struct node));
               temp->data=item;
               temp->next=NULL;
               headB=temp;
           }
           else
           {
            temp->next=(struct node*)malloc(sizeof(struct node));
            temp=temp->next;
            temp->data=item;
            temp->next=NULL;
           }
           printf("\nDo you want to continue[1/0]: ");
           scanf("%d",&cont);
          }while(cont==1);
          break;
  default: printf("\nError, something went wrong");
 }
}


EmoticonEmoticon