Question

I am trying to add two linked-list based integers, but the program keeps giving me the incorrect result. I am trying to add (List 1: 43135) + (List 2: 172). I have pasted the code below

#include <iostream>
using namespace std;

//Linked list node
class Node
{
   public:
   int num;
   Node* next;
};

//Function to create a new node with given numbers
Node *new_Node(int num)
{
   Node *newNode = new Node();
   newNode->num = num;
   newNode->next = NULL;
   return newNode;
}

//Function to insert a node at the beginning of the Linked List
void push(Node** head, int newNum)
{
   Node* newNode = new_Node(newNum);

   newNode->next = (*head);

   (*head) = newNode;
}

// Function to add two linked lists and return the head node of the list
Node* addTwoLists (Node* first, Node* second)
{
   Node* result = NULL;
   Node *temp, *prev = NULL;
   int carry = 0, sum;

//the while loop will perform various calculations on the linked-list
// the loop will execute while both lists exist
   while (first != NULL || second != NULL)
   {
       sum = carry + (first? first->num: 0) +(second? second->num: 0);

       carry = (sum >= 10)? 1 : 0;

       sum = sum % 10;

       temp = new_Node(sum);

       if(result == NULL)
           result = temp;

       else
           prev->next = temp;
           prev = temp;

       if (first) first = first->next;
       if (second) second = second->next;
   }

   if (carry > 0)
   temp->next = new_Node(carry);
   return result;
} //end of while loop

//Function to print the linked list
void printList(Node *node)
{
   while(node != NULL)
   {
       cout << node->num << " ";
       node = node->next;
   }
   cout<<endl;
}

//main function
int main()
{
   Node* result = NULL;
   Node* first = NULL;
   Node* second = NULL;

   // create first list
push(&first, 5);
   push(&first, 3);
   push(&first, 1);
   push(&first, 3);
   push(&first, 4);
   cout <<"First List is ";
   printList(first);

   // create second list
   push(&second, 2);
   push(&second, 7);
   push(&second, 1);
   cout<<"Second List is ";
   printList(second);

   //results of the two lists after it has been added
   result = addTwoLists(first, second);
   cout<<"The sum of the two linked-lists is ";
   printList(result);

return 0;
}

Answer 1

#include <iostream>
using namespace std;

//Linked list node
class Node
{
public:
int num;
Node* next;
};

//Function to create a new node with given numbers
Node *new_Node(int num)
{
Node *newNode = new Node();
newNode->num = num;
newNode->next = NULL;
return newNode;
}

//Function to insert a node at the beginning of the Linked List
void push(Node** head, int newNum)
{
Node* newNode = new_Node(newNum);

newNode->next = (*head);

(*head) = newNode;
}

// Function to add two linked lists and return the head node of the list
Node* addTwoLists (Node* first, Node* second)
{
   //the problem with this code is logic, two add integers, you have to add from the end
   //but you are adding from begining, otherwise everything is fine
   //one way to simply, is, add integers in linked list in reverse order
   //so, that your code will work correctly
   //i, have modified, so that it work as desired
Node* result = NULL;
Node *temp, *prev = NULL;
int carry = 0, sum;

//the while loop will perform various calculations on the linked-list
// the loop will execute while both lists exist
while (first != NULL || second != NULL)
{
sum = carry + (first? first->num: 0) +(second? second->num: 0);

carry = (sum >= 10)? 1 : 0;

sum = sum % 10;

temp = new_Node(sum);

if(result == NULL)
result =prev= temp;//modified here

else
prev->next = temp;
prev = temp;

if (first) first = first->next;
if (second) second = second->next;
}

if (carry > 0)
temp->next = new_Node(carry);
return result;
} //end of while loop

//Function to print the linked list
void printList(Node *node)//modified here
{if(node ==NULL)return;
printList( node->next);
cout << node->num << " ";


}

//main function
int main()
{
Node* result = NULL;
Node* first = NULL;
Node* second = NULL;

// create first list
//modified here also
push(&first, 4);
push(&first, 3);
push(&first, 1);
push(&first, 3);
push(&first, 5);
cout <<"First List is ";
printList(first);
   cout<<endl;
// create second list
push(&second, 1);
push(&second, 7);
push(&second, 2);
cout<<"Second List is ";
printList(second);
cout<<endl;
//results of the two lists after it has been added
result = addTwoLists(first, second);
cout<<"The sum of the two linked-lists is ";
printList(result);

return 0;
}

output:

First List is 4 3 1 3 5
Second List is 1 7 2
The sum of the two linked-lists is 4 3 3 0 7

Process exited normally.
Press any key to continue . . .

//PLS give a thumbs up if you find this helpful, it helps me alot, thanks.