Question

Using C++,

you will create a program, where you will create two doubly linked lists. These doubly linked lists will contain integers within them. Using the numbers in both of these linked lists, you add the numbers together, and insert the addition of the two numbers into a singly linked list.

the input can be from the user or you just write the input.

for example, if one number in the doubly linked list is 817 and in the other linked list has 43, you would add these two numbers, 860 and insert this number into the single linked list

(If you want some ideas: You can traverse the list backwards to add the numbers. the void add function can be: void add(node* tail of linked list1, node* tail of linked list 2, node*head of singly linked list)

Answer 1

Please find the code:

#include <iostream>
using namespace std;
//define a struct node for Double Linked List(DLL) 1
struct Node { 
   int data; 
   struct Node *prev; 
   struct Node *next; 
}; 
struct Node* head = NULL; //points to first node of DLL
struct Node* tail = NULL; //points to last node of DLL
//define a struct node2 for Double Linked List(DLL2) 2
struct Node2 { 
   int data2; 
   struct Node2 *prev2; 
   struct Node2 *next2; 
}; 
struct Node2* head2 = NULL;//points to first node of DLL2 
struct Node2* tail2 = NULL; //points to last node of DLL2
//define a struct Node_LL for Single Linked List(SLL) 
struct Node_LL { 
   int data_LL; 
   struct Node_LL *next_LL; 
}; 
struct Node_LL* head_LL= NULL;//points to first node of SLL   
//insert data into DLL
void insert(int newdata) { 
   struct Node* newnode = (struct Node*) malloc(sizeof(struct Node)); //create a new node
   newnode->data  = newdata; //set newdata as the data of newly created node
   newnode->prev = NULL; // set previous pointer as null
   newnode->next = head; //make next point to head    
   if(head !=  NULL) 
      head->prev = newnode ; //set prev for head as the newnode
   else
     tail=newnode; //make tail point to the last node(only when head=null)
   head = newnode; 
}  
//insert data into DLL2
void insert2(int newdata2) { 
   struct Node2* newnode2 = (struct Node2*) malloc(sizeof(struct Node2)); 
   newnode2->data2 = newdata2; 
   newnode2->prev2 = NULL; 
   newnode2->next2 = head2;     
   if(head2 !=  NULL) 
      head2->prev2 = newnode2 ; 
   else
    tail2=newnode2;
      head2 = newnode2; 
}
//insert data into SLL
void insert_LL(int new_data_LL) { 
   struct Node_LL* new_node_LL = (struct Node_LL*) malloc(sizeof(struct Node_LL)); 
   new_node_LL->data_LL= new_data_LL; 
   new_node_LL->next_LL = head_LL; 
   head_LL = new_node_LL; 
   
} 
//function to add the values in double linked lists and store it into SLL
void add(struct Node* ptr,struct Node2* ptr2,struct Node_LL* ptr_LL) { 
  
  
  while(ptr!=NULL){
      insert_LL(ptr->data+ptr2->data2);//add and insert data
      ptr = ptr->prev; //increment the pointers
      ptr2 = ptr2->prev2; 
  }
  
} 
//display contents of both DLL
void display_DLL() { 
     struct Node* ptr;
     ptr=head;
    cout<<"The doubly linked list is: ";
   while(ptr != NULL) { 
       
      cout<< ptr->data <<" "; 
      ptr = ptr->next; 
  } 
  struct Node2* ptr2;
     ptr2=head2;
  cout<<"\nThe second doubly linked list is: ";
   while(ptr2 != NULL) { 
      cout<< ptr2->data2 <<" "; 
      ptr2 = ptr2->next2; 
  } 
}
//display contents of SLL(Result)
void display_SLL()
{  cout<<" \n";
   cout<<"Resut(Single Linked List): "; 

     struct Node_LL* ptr_LL;
     ptr_LL = head_LL;
    while (ptr_LL != NULL) { 
       
      cout<< ptr_LL->data_LL <<" "; 
      ptr_LL = ptr_LL->next_LL; 
   } 
}
int main() { 
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(817);
  
   insert2(8);
   insert2(7);
   insert2(66);
   insert2(20);
   insert2(43);
 
   struct Node* tail_DLL1;
   tail_DLL1 = tail; 
   struct Node2* tail_DLL2;
   tail_DLL2 = tail2;  
   struct Node_LL* head_SLL;
   head_SLL = head_LL;
   display_DLL();
   add(tail_DLL1,tail_DLL2,head_SLL);//pass tail of DLL,DLL2 and head of SLL for adding and inserting.
   display_SLL();
   return 0; 
}