CareerCup

Use simple maths principles of face and place values.
Traverse list one (eg.5->6->3 ) multiply each digit with 10^n ,where n is nodecount starting at 0 and add the result. This would be 5*10^0 + 6*10^1+ 3*10^2 = 365
Similarly do for list 2 nd regular '+' operator.
Then to form a new resultant list take mod of 10 which will be the ones place,divide the number by 10, then loop this
Eg. 613
613%10 -> 3
613/10 =61; 61%10 -> 1 (item 2 in list)
61/10 =6 ; 6%10 -> 6 (item 3 in list )

Node addTwoLists(ref Node head1, ref Node head2)
        {
            Node head3 =null;
            Node currOfHead1 = head1;
            Node currOfHead2 = head2;
            int sum = currOfHead1.data + currOfHead2.data;
            int carry = Math.Abs(sum / 10);

            if(head1 == null || head2 == null)
            return null;
            while (currOfHead1!=null && currOfHead2!=null)
            {
                 AppendToHead(ref head3, (sum % 10) + carry);     
                 currOfHead1 = currOfHead1.next;
                 currOfHead2 = currOfHead2.next;
            }
            if (currOfHead1 == null)
            {
                sum = currOfHead2.data;
                AppendToHead(ref head3, (sum % 10)+carry);
            }
            else
            if (currOfHead2 == null)
                {
                    sum = currOfHead1.data;
                    AppendToHead(ref head3, (sum % 10) + carry);
                }
            return head3; 
        }

Here a compact solution:

Node sum(Node a, Node b, boolean carry)
{
        if(a == null && b == null && !carry)
            return null;
            
        if(a == null && b == null && carry)
            return new Node(1);
        
        int result = 0;
        
        if(a != null)
            result += a.value;
            
        if(b != null)
            result += b.value;
            
        if(carry)
            result++;
            
        Node res = new Node(result % 10);
        
        Node term1 = a != null ? a.next : null;
        Node term2 = b != null ? b.next : null;
        boolean carry1 = result > 9;
        
        res.next = sum(term1, term2, carry1);
        
        return res;
    }

node * add_lists(node *h1, node *h2) {
  int carry = 0, sum = 0;
  node *sum_list = malloc(sizeof(node));
  node *sum_list_current = sum_list;
  while(h1 != NULL && h2 != NULL) {
    sum = h1->data + h2->data + carry;
    carry = sum/10;
    sum %= 10;
    push(&(sum_list_current->next), sum);
    sum_list_current = sum_list_current->next;
    h1 = h1->next;
    h2 = h2->next;
  }
  while(h1 != NULL) {
    sum = h1->data + carry;
    carry = sum/10;
    sum %= 10;
    push(&(sum_list_current->next), sum);
    sum_list_current = sum_list_current->next;
    h1 = h1->next;
  }
  while(h2 != NULL) {
    sum = h2->data + carry;
    carry = sum/10;                                                                                                                                                                                         
    sum %= 10;
    push(&(sum_list_current->next), sum);
    sum_list_current = sum_list_current->next;
    h2 = h2->next;
  }
  if(carry > 0) {
    push(&(sum_list_current->next), carry);
  }
  node *next = sum_list->next;
  free(sum_list);
  return next;
}

whats free(sum_list)? didnt understand..? arent the above codes not the same?

reverse the two linked lists (which can be done in O(n) ), simulate normal addition with carry, and reverse the final linked list again.

public static void main(String[] args) {
		LinkedList<Integer> l1 = arr2ll(3, 6, 5);
		LinkedList<Integer> l2 = arr2ll(1, 2, 3);
		
		LinkedList<Integer> l = new LinkedList<Integer>();
		int car = 0;
		for(Iterator<Integer> i1 = l1.iterator(), i2 = l2.iterator(); i1.hasNext() || i2.hasNext(); ){
			int n1 = i1.hasNext() ? i1.next() : 0;
			int n2 = i2.hasNext() ? i2.next() : 0;
			int sum = (n1 + n2 + car) % 10;
			l.add(sum);
			car = (n1 + n2 + car) / 10;
		}
		if(car > 0)
			l.add(car);
		
		printLL(l);
	}
	
	public static void printLL(LinkedList ll)
	{
		for(Iterator iter = ll.iterator(); iter.hasNext();)
			System.out.println(iter.next());
	}
	
	public static <T extends Object> LinkedList<T> arr2ll(T...arr){
		LinkedList<T> ll = new LinkedList<T>();
		for(T t : arr)
			ll.add(t);
		return ll;
	}

Entire working code below:

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

typedef struct Digits digit;

typedef struct Digits
{
	int value;
	digit *next;
}digit;

digit* convert2list(int number);
digit* add(digit *num1_list, digit *num2_list, int carry);
int convert2int(digit *num_list);

void main()
{
	int num1, num2, sum;
	digit *num1_list, *num2_list, *sum_list;
	printf("enter the two positive numbers: ");
	scanf("%d%d", &num1, &num2);
	num1_list = convert2list(num1);
	num2_list = convert2list(num2);
	sum_list = add(num1_list, num2_list, 0);
	sum = convert2int(sum_list);
	printf("\n %d + %d = %d", num1, num2, sum);
	printf("\nenter any character to exit: ");
	scanf("%d", num1);
}

digit* convert2list(int number)
{
	digit *node;
	if (number == 0)
		return NULL;
	node = (digit*)malloc(sizeof(digit));
	node->value = number%10;
	node->next = convert2list(number/10);
	return node;
}

int convert2int(digit* num_list)
{
	if (num_list == NULL)
		return 0;
	else
		return num_list->value + 10*convert2int(num_list->next);
}

digit* add(digit* num1_list, digit* num2_list, int carry)
{
	int sum_digits;
	digit *node;
	if (num1_list == NULL && num2_list == NULL && carry == 0)
		return NULL;

	node = (digit*)malloc(sizeof(digit));
	sum_digits = carry + (num1_list!=NULL?num1_list->value:0) + (num2_list!=NULL?num2_list->value:0);
	node->value = sum_digits%10;
	node->next = add((num1_list!=NULL?num1_list->next:NULL), (num2_list!=NULL?num2_list->next:NULL), sum_digits/10);
	return node;
}

Node* list_sum(Node* A, Node* B) {
  if (!A || !B) return NULL;
  Node* head = NULL;
  Node* prev = NULL;
  int carry = 0;
  while (A || B) {
    int sum = 0;
    if (A) { sum += A->val; A = A->next; }
    if (B) { sum += B->val; B = B->next; }
    sum += carry;
    sum = sum % 10;
    carry = sum / 10;
    Node* sum_node = new Node(sum);
    if (!prev) head = prev = sum_node;
    else { prev->next = sum_node; prev = sum_node; }
  }
  return head;
}

Other than the recursive solution, we can also use STACKS. Below is the pseudocode

Push all nodes in list1 to Stack1
Push all nodes in list2 to Stack2
Simply pop from each stack and add the result to Stack 3
Finally pop Stack3 and create the output linked list.

Obviously this uses more space than the standard recursive approach.

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

typedef struct node
{
struct node *next; // the reference to the next node
int data; // will store information
} node;

node* Insert(node *temp, node **h)
{

temp->next=*h; // store the address of the pointer head(second field)
h = &temp; // transfer the address of 'temp' to 'head'
return *h;

}

node * reverse( node * ptr )
{
node * temp;
node * previous = NULL;
while(ptr != NULL) {
temp = ptr->next;
ptr->next = previous;
previous = ptr;
ptr = temp;
}
return previous;
}


node* SumLists(node *a, node *b)
{
node* sum = NULL;

int carry = 0;

while (a!=NULL && b!=NULL) {
int tmp = a->data + b->data + carry;
carry = 0;
if (tmp >= 10) {
carry = 1;
tmp = tmp%10;
}

node* current = (struct node*)malloc(sizeof(node));
current->data = tmp;
sum = Insert(current, &sum);


a = a->next;
b = b->next;
}

while(a!=NULL) {
node* current = (struct node*)malloc(sizeof(node));
int tmp = a->data+carry;
if (tmp>10) {
carry = tmp%10;
}
else {
carry = 0;
}

current->data = tmp;

sum = Insert(current, &sum);

a = a->next;
}

while(b!=NULL) {
node* current = (struct node*)malloc(sizeof(node));
int tmp = b->data+carry;
if (tmp>10) {
carry = tmp%10;
}
else {
carry = 0;
}

current->data = tmp;

sum = Insert(current, &sum);

b = b->next;
}

if(carry != 0)
{
node* current = (struct node*)malloc(sizeof(node));
current->data = carry;
sum = Insert(current, &sum);
}

//sum = reverse(sum);

return sum;
}

int main()
{
struct node *head = NULL; //empty linked list
int i = 0;
int a = 0;
for (i; i<3; i++) {
struct node* temp = (struct node*)calloc(1, sizeof(struct node));
temp->data = i; // store data(first field)
head = Insert(temp, &head);
}


struct node *head1 = NULL;
i=0;
int j = 2;
for (i; i<3; i++) {
struct node* temp = (struct node*)calloc(1, sizeof(struct node));
temp->data = j+7; // store data(first field)
head1 = Insert(temp, &head1);
}

node* tmp = head;
while (tmp != NULL) {
printf("%d",tmp->data);
tmp = tmp->next;
}

printf("------\n");

tmp = head1;
while (tmp != NULL) {
printf("%d",tmp->data);
tmp = tmp->next;
}

printf("------\n");


head = reverse(head);
head1 = reverse(head1);

head = SumLists(head, head1);

printf("sum=");
while (head != NULL) {
printf("%d",head->data);
head = head->next;
}

printf("\n");


}

struct node * add_sum_number_llist(struct node *list_one,
                                   struct node *list_two ){
    int carry = 0, num_one = 0, num_two = 0, temp_sum = 0, sum=0;
    struct node *ret_list = NULL ;
    
    while( (NULL != list_one) || (NULL != list_two)){
        num_one = 0 ;
        num_two = 0 ;
        if (NULL != list_one){
            num_one = list_one->value ;
            list_one = list_one->next ;
        }
        if (NULL != list_two){
            num_two = list_two->value ;
            list_two = list_two->next ;
        }
        temp_sum = num_one + num_two + carry ;
        sum *= 10 ;
        sum += temp_sum % 10 ;
        temp_sum /= 10 ;
        carry = temp_sum % 10 ;
        
    }
    sum *= 10 ;
    sum += carry ;
    while (sum != 0){
        insert(&ret_list, sum % 10 );
        sum /= 10 ;
    }
    return ret_list ;
}

Java implementation. I see there are already several solutions posted for this problem.
I just wanted to put my solution out there for feedback.

Implementation takes in the head node of 2 linked lists as input and returns the node head of the linked list that contains their sum. The first portion of the addList method iterates through the 2 input list and adds each node until the end of the shortest input list is reached. If both list are the same length we are done. Assuming the number in a node ranges from 0 to 9 (going off the example), then the carry over to the next significant node will always be 1 and the data left in the current node will be (currentSum - 10). E.g. if you add 9 + 9 = 1(carry over to next node)8(current node sum). The second part of the adds the remaining nodes to the output node if we happened to have list of different lengths (i.e. one of the input list reaches null before the other). In this case the short list node entries are treated as 0 entries, which is equivalent to just copying the longer list node entries over.

public class Node{
 public Node next;
 public int data;
}

static Node addList(Node listOne, Node listTwo){
 int carryOver = 0;
 int dataSum = 0
 Node sum = new Node();
 Node currentNode = sum;

 while(listOne != null || listTwo != null){
  dataSum = ((listOne != null) ? listOne.data : 0) + ((listTwo != null) ? listTwo.data : 0)
  dataSum += carryOver;
  carryOver = 0;

  if(dataSum > 10 ){
   carryOver = 1;
   dataSum -=10;
   }

  currentNode.data = dataSum;
  currentNode.next = new Node();
  currentNode = currentNode.next;
  listOne = (listOne != null) ? listOne.next : null;
  listTwo = (listTwo != null) ? listTwo.next : null;
 }

 if(carryOver){
  currentNode.data = 1;
 }

 currentNode.next = null;
 return(sum);
}

Its simple as folllows.

Node * addLists(Node *n1,Node *n2,int carry)
{
	if(n1==NULL && n2==NULL)
	{
		return NULL;
	}
	Node *n3=new Node;
	int value=carry;
	if(n1!=NULL)
	{
		value+=n1->data;
	}
	if(n2!=NULL)
	{
		value+=n2->data;
	}
	n3->data=value%10;
	Node *res=addLists(n1->next,n2->next, value>=10 ? 1 : 0);
	n3->next=res;
	return n3;
}

public class AdditionOfTwoList {

	public static void add(LinkedList<Integer> l1, LinkedList<Integer> l2) {
		if (l1 == null || l1.size() == 0 || l2 == null || l2.size() == 0) {
			return;
		}
		int s1 = l1.size();
		int s2 = l2.size();

		LinkedList<Integer> result = new LinkedList<Integer>();
		int carryIn = 0;
		int s = s1 < s2 ? s1 : s2;
		for (int i = 0; i < s; i++) {
			int a = l1.get(i);
			int b = l2.get(i);
			int c = a + b + carryIn;
			carryIn = 0;
			if (c > 9) {
				c = c - 10;
				carryIn = 1;
			}
			result.add(c);
		}
		if (s1 < s2) {
			for (int i = s1; i < s2; i++) {
				int c = l2.get(i) + carryIn;
				carryIn = 0;
				result.add(c);
			}
		} else if (s1 > s2) {
			for (int i = s2; i < s1; i++) {
				int c = l1.get(i) + carryIn;
				carryIn = 0;
				result.add(c);
			}
		} else {
			if (carryIn == 1) {
				result.add(1);
			}
		}
		for (Integer i : result) {
			System.out.print(i + " ");
		}
	}

	public static void main(String[] args) {
		LinkedList<Integer> l1 = new LinkedList<Integer>();
		LinkedList<Integer> l2 = new LinkedList<Integer>();
		l1.add(5);
		l1.add(6);
		l1.add(3);
		
		l2.add(8);
		l2.add(4);
		l2.add(2);
		add(l1,l2);
	}
}