CareerCup

1-2-3 and 4-5-6 , just traverse thru linked list as ((1*10+2)*10+3)+((4*10+5)*10+6) this should give correct result . O(n+m) where n and m are the length of linked list.

All the answers that are converting the list to numbers or the result to a number are false if the numbers are very large.

Another solution could be

Create reverse of the two linked lists(rev1, rev2)
Now we can easily run through these lists rev1, rev2 element by element and do additions of their corresponding values to create a new list rev3.
Also make sure to pass the carries to next element. In the end if we have carry but both lists have exhausted, we will need to create a new element for the carry also in rev3.
Reverse this new list rev3 to get the final answer.

This solution does require additional space to store the intermediate reverse lists.

You are thinking both list has the same size!! and if you look and the second example you gonna see that can have a list with different sizes!! the solutions are wrong if you only think and sum all the numbers on each list!

My solution
1. traverse the nodes and store each node in a seperate stack for each list.
2. for each element from each stack, put the sum in a diferent stack if one of the stack is empty continue with the other one until you have both stacks empty
3. then remove each element from the stack and add to a Linked list using the AddElement totail.

Reverse the both lists and then send them as argument of the below function. Again reverse the list for the final result. The function handles every case.

struct node* addTwoLists (struct node* first, struct node* second)
{
    struct node* res = NULL; 
    struct node *temp, *prev = NULL;
    int carry = 0, sum;
 
    while (first != NULL || second != NULL) //while both lists exist
    {
        
        sum = carry + (first? first->data: 0) + (second? second->data: 0);        
        carry = (sum >= 10)? 1 : 0;        
        sum = sum % 10; 
      
        temp = newNode(sum);
        
        if(res == NULL)
            res = temp;
        else
            prev->next = temp;       
        prev  = temp; 
        if (first) first = first->next;
        if (second) second = second->next;
    }
 
    if (carry > 0)    // when additional carry generated, make a new node with data as carry value.
      temp->next = newNode(carry); 
  
    return res;
}

struct node *newNode(int data)
{
    struct node *new_node = (struct node *) malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

1. traverse the nodes and store each node in a seperate stack for each list.
2. pop nodes from two stacks, add them, and make it point to the previous added node.
3. repeat the step 2 till there are nodes in both the stacks.
4. pop non empty stack and point it to previous node. do this untill the stack has a node.

Convert first list to a number
Convert second list to a number
sum the numbers
create and return new list representing the sum

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

typedef struct node_type {
struct node_type *next;
int value;

} node;

int sum_of_list (node *curnode) {
int sum = 0;


while (curnode) {
sum *= 10;
sum += curnode->value;
curnode = curnode->next;
}

return sum;

}

void free_list (node *head) {
node *next = NULL;

while (head) {
next = head->next;
free (head);
head = next;
}
}

node* create_list (int value) {
node *head = NULL, *new = NULL;
int cur_value = 0;


while (value) {

cur_value = value % 10;
new = (node*) malloc(sizeof(node));
if (!new) {
printf("Not enough memory\n");
free_list(head);
return NULL;
}

new->value = cur_value;
new->next = head;
head = new;
value /= 10;
}

return head;
}


node * sum_list (node* list1, node* list2) {


int sum1 = 0, sum2 = 0;

if (!list1 && !list2) {
return NULL;
}

sum1 = sum_of_list(list1);
sum2 = sum_of_list(list2);

return create_list(sum1 + sum2);

}


main () {
char q[10];
int number1;
int number2;
node *head1 = NULL, *head2 = NULL, *sum_head = NULL;
int sum;

do {
printf("\nNumber1:");
scanf("%d", &number1);
head1 = create_list(number1);

printf("\nNumber2:");
scanf("%d", &number2);
head2 = create_list(number2);

sum_head = sum_list(head1, head2);
printf ("\nsum: %d", sum_of_list(sum_head));
free_list(head1);
free_list(head2);
free_list(sum_head);

printf("\nEnter quit or anything else to continue: ");
scanf("%s", q);
} while (strcmp(q, "quit") != 0);

Assumption is that they are the same length.

When you reach the end of the list (nil or null), return 0.
Otherwise, pass the remainder of the lists to the programs, adding the sum of the first two elements to each list into a new list called zs.

(defun sum-lists (xs ys zs)
    (if (= xs nil) 0
        (sum-lists (cdr xs) (cdr ys) (cons (+ (car xs) (car ys)) zs))))