Description: You are given two pointers to two linked lists. Each linked list represents a number. Your task is to write a function to form the sum list by adding the numbers of the two lists.

I f video does not load, Click here

First List: 1->2->6 // represents number 621

Second List: 9->2 // represents number 29

Output

Sum list: 0->5->6 // represents number 650

Algorithm:

Loop through both linked lists and repeat the following:

1) One by one pick nodes from both list and add their values.

2) If sum is more than 10 then set carry as 1 and reduce sum.

3) Create a new node with sum as data

4) if this is the first node then set it as head of the resultant list

5) else if this is not the first node then connect it to the rest

6) Set prev for next iteration

7) Move first and second pointers to next nodes

After the loop is over, if carry is still>0, create a new node and add it to the listand finally return head.

C Implementation:

/* Linked list node */

structnode

{ int data;

structnode* next;

};

/* Function to create a new node */

structnode *newNode(intdata)

{

structnode *new_node = (structnode *) malloc(sizeof(structnode));

new_node->data = data;

new_node->next = NULL;

return new_node;

}

/* Function to add two linked lists */

structnode* addTwoLinkedLists (structnode* first, structnode* second)

{

structnode* res = NULL; // res is head node of the resultant list

structnode *temp, *prev = NULL;

intcarry = 0, sum;

/* One by one pick nodes from both list and add their values. */

while(first != NULL || second != NULL)

{ sum = carry + (first? first->data: 0) + (second? second->data: 0);

/* If sum is more than 10 then set carry as 1 and reduce sum */

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

sum = sum % 10;

/* Create a new node with sum as data */

temp = newNode(sum);

/* if this is the first node then set it as head of the resultant list */

if(res == NULL)

res = temp;

else

/* If this is not the first node then connect it to the rest. */

prev->next = temp;

/* Set prev for next insertion */

prev = temp;

/* Move first and second pointers to next nodes */

if(first) first = first->next;

if(second) second = second->next;

}

/* if carry is still>0, create a new node and add it to the list */

if(carry > 0)

temp->next = newNode(carry);

/* finally return head */

return res;

}

Time Complexity:

O(m + n) where m and n are number of nodes in first and second lists