CareerCup

It's a simple mathematics problem and no additional DS or additional traversal
are required. Just do a single traversal of both LL's from start to end,
and add up the current two values (CRV=L1[i] + L2[i]), multiply the stored
accumulator by 10 and add the CRV.

Below is the pseudo code:

L1[], L2[], CRV = 0, RES=0
for (i = 0; i < L1.size(); ++i)
{
    CRV = L1[i] + L2[i]
    RES = RES * 10
    RES = RES + CRV
}

That's all.

try it recursively..
first go to end of both the list.
from there start adding number and return the carry number.
while in each recursion add the numbers and carry number.
at the end when we reach to the first nodes i.e. the MSB of the number add these and get the carry number. if that carry number is non zero then add one more node to the head with that value.

Assuming the first list is list1,
second list is list2, result has to be stored in list3
if ((list1==null) and (list2==null))
{
list3==null;
}

If (list1 == null)
//traverse through list 2 and assign list3 = list2

if(list2 == null)
//traverse through list 1 and assign list3=list1

//assuming all error cases are handled

consider this function

int carry =0 ;
add(struct node *list1, struct node *list2, struct node **list3, int *carry)
{
	carry = 0;
	if((list1->next) && (list2->next))
	{
		add(list1->next, list2->next, &list3->next, &carry);
	}
	*list3->data = list1->data + list2->data + *carry;
	if(*list3->data > 10)
	{
		*list3->data = *list3->data % 10;
		*carry = 1;
	}
}

if carry exists then one more linked list node has to be created at head node to accomodate carry.

We can use a helper data structure? like stack?
If so, we can iterate both lists. push elements of list1 to stack1, push elements of list2 to stack2.

Than start popping elements from the stack (elem1 from stack1, elem2 from stack2):
adds them and put the new value in the beginning of the new list we are building...
something like:

previous_carry = 0;
ret_list = NULL;

while (!stack1.empty())
{
   elem1 = stack1.pop();
   elem2 = stack2.pop();
   elem3 = elem1 + elem2 + previous_carry;
   if (elem3 >= 10)
   {
     previous_carry = elem3 - 10;
     elem3 %= 10;
   }
   else
   {
      previous_carry = 0
   }
   Node curr_node = nww Node;
   curr_node.val = elem3;
   curr_node.next = ret_list;
   ret_list = curr_node;
}
return ret_list;

}

Use lazy evaluation of recursion. So technically the unfolding of recursion is not a traversal.
So,
h1 and h2 are the heads, h3 is the result. h3 could have length 1 greater than that of h1.
Ive written a quick sample here..

add(h1, h2) {
 if(isNull(h1) || isNull(h2))
   return null;
	 
 h3 = new LinkedList(size(h1) + 1);
 carry = add2(h1, h2, next(h3));
 value(h3) = carry;
 return h3; 	

}

add2(h1, h2, h3) {
	if(isLast(h1)) {
		carry = 0;
		if(value(h1)+value(h2) > 10) {
			value(h3) = 0;
			carry = (value(h1)+value(h2))%10;
		}
		else {
			value(h3) = value(h1)+value(h2);
		}

	}
	else {
		carry = add2(next(h1), next(h2), next(h3));
		sum = carry + value(h1) + value(h2);
		if(sum > 10) {
			value(h3) = 0;
			carry = sum % 10;
		}
		else {
			carry = 0;
			value(h3) = sum;
		} 		
	
	}
	return carry;	
	

}
}

int Count(List* first, List* second)
{
	if(!first || !second)
	return;
	Stack numbers = new Stack();
	while(first)
	{
		numbers.push(first->data + second->data);
		first = first->next;
		second = second->next;
	}
	int count = 0;
	for(int i = 0; !numbers.Empty(); ++i)
	{
		int num = numbers.Pop();
		if(i == 0)
			count = num;
		else
			count += (num << (3*i)) + (num << i);
	}
	return count;
}

public static Integer addList(LinkedList listone, LinkedList listtwo){

int carryover = 0;
int tempsum = 0;
int carryoverindex = 0;

StringBuilder sumbuild = new StringBuilder();



for(int i=listone.size()-1;i>=0;i--){


    
if((carryoverindex - 1) != i){
carryover = 0;
}


tempsum = (int)listone.get(i) + (int)listtwo.get(i) + carryover;

if(tempsum > 9 && (i != 0)){
carryoverindex = i;
carryover = (tempsum-(tempsum - 10))/10;
tempsum = tempsum - 10;
if (carryover == 0){
carryover = 1;
tempsum = 0;
}

}

//System.out.println(sumbuild+" "+i+" "+"before "+tempsum);
sumbuild.append(tempsum);



}
return Integer.parseInt((sumbuild.reverse()).toString());

}

Logic:
recursion is one of the best solution for this problem
but yes it will be considered as 2 traversal of input list
because
one time traversal means one you analysed the the node and moved out don't come back to that node again.... whereas in our case one time we check whether the node is not null to get end point for node and second time we analysed the node to perform adding operation.
so 2 traversal..... it seems :)

If extra space is not a problem, the below approach should work.

1) Compute two integers by parsing the first two lists (assuming the numbers stored in the list are within integer's size. If not, any of the recursive solutions in this thread should be fine).
2) Add both the integers and store it in a resultant variable
3) Break down the digits in the resultant variable and store it in the third list

Here is recursive solution in java.

private static int listSize(ListNode node) {
        if (node == null) return 0;
        return listSize(node.next) + 1;
    }

    public static int sumLinkedLists (ListNode list1, ListNode list2) {
        return sumLinkedLists(list1, list2, listSize(list1) - 1);
    }

    private static int sumLinkedLists (ListNode list1, ListNode list2, int digitPos) {

        if (list1 == null || list2 == null) return 0;

        int recursiveSum = sumLinkedLists(list1.next, list2.next, digitPos - 1);

        int sum = list1.data + list2.data;

        recursiveSum = recursiveSum + sum * (int) Math.pow(10, digitPos);
        return recursiveSum;

    }

struct Node * RecurAddWrap(struct Node *first,struct Node *second,int &carry)
{
if(!first && !second)
return NULL;
struct Node *local=RecurAddWrap(first->next,second->next,carry);
int sum=first->data + second->data+carry;
carry=sum>=10?1:0;
struct Node *temp=NewNode(sum>=10?sum%10:sum);
temp->next=local;
return temp;
}
struct Node * RecurAdd(struct Node *first,struct Node *second)
{
int carry=0;
struct Node *res=RecurAddWrap(first,second,carry);
if(carry)
{
struct Node *t=NewNode(carry);
t->next=res;
return t;
}
else
return res;
}

The problem can be solved if you can handle the carry... there are two cases to handle the carry... 1 is if 9 + 9 = 18. in that case we'll receive the carry as the head of the list.
other cases are 99 + 99 = 198 in which we've to add the carry to the previous node. just little paper and pencil will ensure that we'll never have a carry greater than 1 and we'll never have a sum%10 greater 8. therefore we just have to handle two cases only.

Following is the algorithm please suggests any improvement.

node* add_list(node* l1, node* l2, node* prev) {

	if (l1 == NULL && l2 == NULL)
		return NULL;

	node* add = new node(0);

	add->item += l1->item;
	add->item += l2->item;

	int carry = add->item / 10;
	add->item = add->item % 10;

	if (carry > 0) {

		if (prev == NULL) {

			prev = new node(carry);
			prev->next = add;
			add->next = add_list(l1->next, l2->next, add);  // case 1
			return prev;

		} else {
			prev->item += carry;
		}
	}

	add->next = add_list(l1->next, l2->next, add);  // case-2
	return add;
}

// Addition may also be so complex :) but google can make it in interview, i think !!
 /*   AUTHOR @ AVANEESH KUMAR2013 ,BIET JHANSI, prmrs111@live.com       */
 
#include<stdio.h>
#include<cstring>
#include<iostream.h>
#include<string.h>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<vector>
#include<set>
#include<complex>
#include<list>
// TOO lazy  :)
using namespace std;
 
#define input(t) scanf("%d",&t)
#define input_ll(t) scanf("%lld",&t)
#define LL long long
#define myfor(i,a,b) for(i=a;i<=b;i++)
#define vi vector <int>
#define pb push_back
//<<<<<<<<<<<<<<<<<<<<<<<<<STARTED>>>>>>>>>>>>>>>>>>>>
vi array1;
vi array2;
int ans[79];
int n,spcarry=0,l;
int carry(int start)
{
if(start==n-1)
{ 

	    ans[start]=(array1[start]+array2[start])%10;
		return (array1[start]+array2[start])/10;
}
else if(start>n-1)
{
	return 0;
}
else
{
    ans[start]=(array1[start]+array2[start]+carry(start+1));	
    if(start==0)
    spcarry=ans[0]/10;
    ans[start]=(array1[start]+array2[start]+carry(start+1))%10;
    return (array1[start]+array2[start]+carry(start+1))/10;
}


}
int main()
{
 int i,temp;
 cout<<"what is the length of arrays?"<<endl;
 cin>>n;
myfor(i,0,n-1)
{
  cin>>temp;
  array1.pb(temp);
}
myfor(i,0,n-1)
{
   cin>>temp;
   array2.pb(temp);
}
 carry(0);
 cout<<spcarry;
myfor(i,0,n-1)
  cout<<ans[i];
}

struct node {
        int x;
        struct node *next;
};


int 
add (struct node *n1, struct node *n2, int *level) {
        int l = 0;
        int sum = 0;
        if (!n1 || !n2) {
                exit(EXIT_FAILURE);
        }   
        if (n1->next == NULL && n2->next == NULL) {
                *level = 1;
                return (n1->x + n2->x);
        } else {
                sum = add(n1->next, n2->next, &l);
                *level = l + 1;
                return (pow(10, l)*(n1->x + n2->x) + sum);
        }   
}

//init flag = 1;
void add_list(struct node *lista, struct node *listb, struct node **target,int flag) {
    if (lista == NULL && listb == NULL) 
        return;
    add_list(lista->next,listb->next,target,0);
    struct node temp,temp1;
    temp = malloc(sizeof(struct node));
    temp->data = lista->data + listb->data;
    if(*target != NULL) {
        if(*target->data >= 10) {
            *target->data = *target->data - 10;
            temp->data = temp->data + 1;
        }
    }    
    temp->next = *target;
    *target = temp;
    
    //Used only for the first iteration and that is why it is messy !!
    if (flag && (*target->data >= 10)) {
        temp1 = malloc(sizeof(struct node));
        temp1->data = 1;
        *target->data = *target->data - 10;
        temp1->next = *target
        *target = temp1;
    }
}

Node* add(Node *n1,Node *n2,int *carry){
      if(!n1)
             return NULL;
      Node *t=add(n1->next,n2->next,carry);
      int sum=n1->data+n2->data+*carry;
      *carry=(sum/10)%10;
      sum=sum%10;
      Node *n=create(sum);
      n->next=t;
      return n;
}
Node *addTwoNums(Node *n1,Node *n2){
     int carry=0;
     Node *t=add(n1,n2,&carry);
     if(!carry)
               return t;
     Node *n=create(carry);
     n->next=t;
     return n;
}

As some mentioned above the recursive solution is the most efficient. Here is my solution in Scala. Wrote it in 'gedit' :)

def add(a: List[Int], b: List[Int]): List[Int] = {
  def addint(pos:Int, carry: Int, a: List[Int], b: List[Int], acc: List[Int]): List[Int] = pos match {
    case i if (i > -1) =>
      val sum = a(pos) + b(pos) + carry
      addint(pos - 1, sum / 10, a, b, sum % 10 :: acc)
    case _ =>
      acc
  }
  addint(a.size - 1, 0, a, b, Nil)
}

To try it paste it to Scala REPL and run:

scala> add(List(1,5), List(2,7))

L1 : 4 -> 5 -> 6
L2 : 4 -> 5 -> 6

result should be a linked list.
L3: 9 -> 1 -> 2

9 <- 1 <- 2

List *add(const List &, const List &)
{
	List result;
	Node *a=L1.head, *b=L2.head;
	Node *result_node = NULL;
	ASSERT(result.head = NULL);
	
	while (a!=NULL && b!=NULL) {
		int vlaue = a->value + b->value;
		int node_value = value%10;
		int carried = value / 10;
		result_node = result.head;
		while(carried && result_node!=NULL) {
			result_node->value = (result_node->value + carried )%10;
			carried = (result_node->value + carried)/10;
			result_node = result_node->next;
		}
		if (carried && !result_node) {
			// add to the beginning
			Node *curr = new Node(carried);
			result.last->next = curr;
			result.last = curr;
		}
		Node *curr = new Node(value);
		curr -> next = result.head;
		result.head = curr;
		if (result.head == NULL) { result.last = curr; }
	}
	
	// now reverse the list result
	
	Node *prev=NULL,*curr=result.head,*next=NULL;
	next = curr->next;
	while(curr) {
		curr->next = prev;
		prev = curr;
		curr = next;
		next = curr->next;
	}
	
	result.head = prev;
}

Here you go. This handles unequal sized lists too.

int[] carriage = new int[Math.max(num1.size(), num2.size())+1];
int[] result = new int[carriage.length];
boolean carr = false;

Iterator<Node> itMax = num1.size()<num2.size()?num2.iterator():num1.iterator();
Iterator<Node> itMin = num1.size()<num2.size()?num1.iterator():num2.iterator();
int n,n1,n2;
int multiplier = (Math.max(num1.size(), num2.size()) - Math.min(num1.size(), num2.size()));
int minSize = Math.min(num1.size(), num2.size());
int maxSize = Math.max(num1.size(), num2.size());

int y=0,x=0;

// Initial sum from left to right. Also maintaining carriages for normalization.
// Parsing the linked list only once.
for(int i=0;itMax.hasNext();i++){
n1 = itMax.hasNext()?(itMax.next()).val:0;
n2 = itMin.hasNext()?(itMin.next()).val:0;
y = (int) (y + n2 * (Math.pow(10,(minSize-1-i))));

n = (n1 + n2);
if(n/10 > 0 || n==10){
carriage[i] = 1;
carr = true;
}
result[i+1] = n%10;
}

//Normalizing
while(carr){
x = 0;
carr = false;
for(int i=1;i<result.length;i++){
if((result[i]+carriage[i])/10>0 || (result[i]+carriage[i])==10){
carriage[i-1] = 1;
carr = true;
}
result[i] = (result[i]+carriage[i])%10;
x = (int) (x + (result[i] * (Math.pow(10,(maxSize-i)))));
carriage[i] = 0;
}
}

//Result Sum
System.out.println("SUM = "+(x-(int)(((Math.pow(10,multiplier))-1)*y)));

int sum = 0;
int count = 0;
int totaCount = 0;


private void sumNode(MyLinkList.Node n1, MyLinkList.Node n2) {
if(n1.next != null){
count++;
if(totaCount < count){
totaCount = count;
}
sumNode(n1.next, n2.next);
}
int ret = n1.val+n2.val;
sum += (ret*Math.pow(10,(totaCount-count)));
count--;
}

Basically adding from back to front node to node and multiplying every node with its decimal position before adding
so

919
935
woule be
Sum += 9+5 = 14*10^0 = 14
sum += 3+1 = 4*10^1 = 40
sum+= 18*10^2 = 1800

sum = 1854

Are you sure without second traversal... it can be done in O(n) but second traversal would be needed

second traversal means ??