Given two non empty Linked List with non negative numbers, and numbers are stored in reverse order having single digit. Add the two list and return the result as a linked list.

Input: [ 3 -> 4 -> 5 ] + [ 1 -> 2-> 3]
Output: [ 8 -> 6 -> 4 ]

Explanation: 543 + 321 = 8 -> 6 -> 4

Detailed Explanation:

The above linked list can be visualized as below:

Let’s take a simple example on how we add on a paper:

   199

+     1

=====

  200

Here we have to take the least significant digit and add it. If the resultant digit is 10 [overflow], then we carry 1. That carry is added to the next digit and solved until it reaches the most significant digit.

In our solution we use the same logic. Below are the steps that we shall be performing:

Step 1: Take a head pointer to both of the lists. Take “result_list” linked list to store the sum.

Step 2: Initialize “sum” and “carry” variables.

            Sum variable will keep track of the total sum.

            Carry variable will check if there is a overflow.

Step 3: Add the first number of list 1 to first number of list 2.

            Calculate if the sum is greater than 10, then update the carry for next calculation.

If the sum is greater than 10, then get the current sum by using “sum = sum % 10” formula.

Step 4: Update the sum in “result _list” linked list.

 Step 5: Go to the next node.

In case, if one node has more nodes than the other, then other list remaining value will be filled by 0.

C program to implement the same:

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

/* create a linked list*/
struct Node {
	int data;
	struct Node *next;

};

/* Create a new node */
struct Node* newNode(int value)
{
	struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
	newNode->data = value;
	newNode->next = NULL;

	return newNode;
}

/*Insert a new node at the begenning*/

void insert_node(struct Node** head_ref, int new_data)
{
    /* create new node */
    struct Node* new_node = newNode(new_data);
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}

/* Print linked list */
void displayList(struct Node *node)
{
    while(node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

/* Add two list number*/


struct Node* addTwoValues(struct Node *first_list, struct Node *second_list)
{
	struct Node *result_list = NULL; // Holds the final list 
	struct Node *temp = NULL; // To create new node for result
	struct Node *prev = NULL; 

	int sum = 0; // To hold sum
	int carry = 0; // to update carry, if present


	  while (first_list != NULL || second_list != NULL) 
    {

        sum = carry + (first_list? first_list->data: 0) + (second_list? second_list->data: 0);
 
        // if carry is present, then update it for next calculation in next iteration.
        carry = (sum >= 10)? 1 : 0;
 
        // update the sum, if it is greater than 10
        sum = sum % 10;
 
        // create a node to update the sum.
        temp = newNode(sum);
 
        if(result_list == NULL)
            result_list = temp;
        else 
            prev->next = temp;
 
        prev  = temp;
 
        if (first_list) first_list = first_list->next;
        if (second_list) second_list = second_list->next;
    }
 
    if (carry > 0)
      temp->next = newNode(carry);
 
    return result_list; 

}


int main(void)
{
    struct Node* res_list = NULL;
    struct Node* first_list = NULL;
    struct Node* second_list = NULL;
 
    // create first list 3->4->5
    insert_node(&first_list, 3);
    insert_node(&first_list, 4);
    insert_node(&first_list, 5);

    printf("First Linked List is ");
    displayList(first_list);
 
    // create second list 1->2->3
    insert_node(&second_list, 1);
    insert_node(&second_list, 2);
    insert_node(&second_list, 3);

    printf("second_list List is ");
    displayList(second_list);
 
    // Add the two lists and see result
    res_list = addTwoValues(first_list, second_list);
    printf("Result list is ");
    displayList(res_list);
 
   return 0;
}