CareerCup

Reverse both lists, compute sum, and then reverse back.

The following approach maynot need any modification to the input strings.

Step 1- Identify input linked list of shorter length(For this purpose, get length of both input string and compare them)----> Its O(n) operation
Step 2 - Traverse the longer length linked list till its remaining length is same as the shorter one ----> Its O(n) operation
Step 3 - Use the recursion to calculate the sum ---> Its O(n) operation

Pseudocode

Calculate ListSum(ptr1,ptr2)
{
ptr1 = Starting node pointer of LL1
ptr2 = Starting node pointer of LL2

Len1 = Length of LL1
Len2 = Length of LL2
if(Len1<Len2)
then 
ptr3 = node pointer after moving ptr1 for (Len2-Len1) nodes
fi
residue = calSum(ptr1,ptr3);
Append nodes of ptr2 (taking care of residue) to output list
Return the result
}

int calSum(ptr1, ptr3)
{
  if(ptr1->next is NULL)
  then 
    value =  ptr1->value + ptr3->value
    if value>9
      then residue = 1, value = value -10;
    fi
    create output list and insert node (having value)
    return residue
   fi
   residue = calSum(ptr1->next + ptr3->next);
   value = residue + ptr1->value + ptr2->value;
    if value>9
      then residue = 1, value = value -10;
    fi
    Append node (having value) in output list;
    return residue;
}













  
}

Is this logic correct?

int sum1 = 0, sum2=0;
While(current1! = NULL)
{
sum1 = sum1*10 + current1->data;
current1 = current1->next;
}

While(current2! = NULL)
{
sum2 = sum2*10 + current2->data;
current2 = current2->next;
}

return (sum1+sum2)

Since we can reverse the list or use recursion. We need to maintain 2 linked lists.
One for Sum other for carry.
As you add Create sum as sum->digit = (num1->digit + num2->digit)%10
Carry->digit = (num1->digit + num2->digit )/10;
next at each iteration: sum->digit = (sum->digit + carry->next->digit)%10
and so on until the carry list vanishes.

traverse first linked list and find the sum
i.e e.g 7->4->5->2
then sum1 = (((((7*10) + 4) *10 ) + 5 ) * 10 +2)

do the same for list 2. Add both sum

This can be implemented using 2 stacks. The code for it is given below:

while(list1!=NULL)
	{
		int temp = list1->element;
		s1.push(temp);
		list1 = list1->next;
	}

	while(list2!=NULL)
	{
		int temp = list2->element;
		s2.push(temp);
		list2 = list2->next;
	}

	while(!list1.isEmpty()&&!list2.isEmpty())
	{
		int sum = 0, carry = 0;
		int num1 = s1.pop();
		int num2 = s2.pop();
		sum = num1 + num2 + carry;
		carry = sum/10;
		s3.push(sum%10);
	}
	while(!list1.isEmpty())
	{
		int sum = 0, carry = 0;
		int num1 = s1.pop();
		sum = num1 + carry;
		carry = sum/10;
		s3.push(sum%10);
	}
	while(!list2.isEmpty())
	{
		int sum = 0, carry = 0;
		int num2 = s2.pop();
		sum = num2 + carry;
		carry = sum/10;
		s3.push(sum%10);
	}
	
	while(!s3.isEmpty())
	{
		int val = s3.pop();
		printf(val);
	}

where in the previous code, list1 and list2 are the 2 lists containing the numbers. s1, s2, s3 are the three stacks used to store the numbers in list1, list2 and the result respectively.

1)Reverse Link List L1
2)Reverse Link List L2
3)Add L1->data and L2->data , if it is greater than 9 then set carry as one
and and store (sum)%10 in new created node.
4)Reverse the newly created link list.

We have take care the following fact
a)length of L1 > length of L2
b)L1 or L2 can be null
c)Last element of L1 and L2 can be 9. So use extra check for this.

For complete program see
"goursaha.freeoda.com/DataStructure/LinkListAddition.html"

Solution already provided
1. Finding Intersection, followed by recursive addition
Deepak on May 19, 2010
2. Reverse, Addition , Reverse.
Anonymous on May 21, 2010

Please correct me if I missed any other genuine solution.

Just thought to share an alternative solution.
Step 1 : Initialization of linked list with adding the degree of the integer.
7541
(7,3) -> (5,2) -> (4,1) -> (1,0) -> NULL
O(m+n)
Step 2 : Recursive addition
Every recurring code snippet wait for carry to return from next call, so as to augment with the node in resultant list.
O(n) , wlog, n>m

Please comment.

@Karthik
the sum you calcualte by traversing the LL may not fit into any datatype(int long double etc) then what will you do ?

<pre lang="java" line="1" title="CodeMonkey58285" class="run-this">import java.util.Random;

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

public static int listToNum(Node n){
int num = 0;
while (n != null) {
num = num*10 + n.data;
n = n.next;
}
return num;
}

private static Node createRandomList(long seed, int count){
Random r = new Random(seed);
Node n, head, temp;
n = new Node();
n.data = r.nextInt(10);
System.out.print("List="+n.data+" ");
head = n;
for (int i=1; i<count; i++){
temp = new Node();
temp.data = r.nextInt(10);
System.out.print(temp.data+" ");
n.next = temp;
n = temp;
}
System.out.println();
return head;
}

public static void main (String args[]) {
Node head1 = createRandomList(1, 4);
Node head2 = createRandomList(2, 3);

int n1 = listToNum(head1);
int n2 = listToNum(head2);
System.out.println(n1+"+"+n2+"="+(n1+n2));
}

}</pre><pre title="CodeMonkey58285" input="yes">
</pre>

<pre lang="java" line="1" title="CodeMonkey27602" class="run-this">import java.util.Random;

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

public static int listToNum(Node n){
int num = 0;
while (n != null) {
num = num*10 + n.data;
n = n.next;
}
return num;
}

private static Node createRandomList(long seed, int count){
Random r = new Random(seed);
Node n, head, temp;
n = new Node();
n.data = r.nextInt(10);
System.out.print("List="+n.data+" ");
head = n;
for (int i=1; i < count; i++){
temp = new Node();
temp.data = r.nextInt(10);
System.out.print(temp.data+" ");
n.next = temp;
n = temp;
}
System.out.println();
return head;
}

public static void main (String args[]) {
Node head1 = createRandomList(1, 4);
Node head2 = createRandomList(2, 3);

int n1 = listToNum(head1);
int n2 = listToNum(head2);
System.out.println(n1+"+"+n2+"="+(n1+n2));
}

}

</pre><pre title="CodeMonkey27602" input="yes">
</pre>

hey i think we can solve this recursivly ...
here i m taking assumption that both linkedlist r of same size.

int sum(Node * s1, Node *s2)
{
static int j=1;
if (s1==NULL || s2 == NULL)
return 0;
int i=sum(s1->next,s2->next);
i=(s1->data+s2->data)*j + i;
return i;
}


it will process like this ...

s1 = 9-8-7-6
s2=9-9-9-9
sum = (6+9)+10*(7+9)+100*(8+9)...

I don't kow what people have been thinking. But isnt this a simple solution???

int calculate_num(Node * root)
       {   int num=0;
           while(root!=NULL)
            {   num=num*10+root->data;
            }
            return num;
       }
       int sum_num_as_list(List l1,List l2)
       {    return(calculate_num(l1.root)+calculate_num(l2.root));
       }

void merge_tree(tree_node_type *t1 , tree_node_type *t2)
{
if(t2)
{
merge_tree(t1 , t2->left);
merge_tree(t1 , t2->right);
insert_node_in_tree(t1 , t2);

}
}


tree_node_type *insert_node_in_tree(tree_node_type *t1 , tree_node_type *t2)
{
if(t1==NULL)
{
t2->left=NULL;
t2->right=NULL;
return t2;
}
if(t2->data<t1->data)
{
t1->left = insert_node_in_tree(t1->left , t2);
return t1;
}
else if(t2->data > t1->data)
{
t1->right = insert_node_in_tree(t1->right , t2);
return t1;
}
else
{
printf("Duplicate , here you can delete the node\n");
free(t2);
return NULL;
}
}

i think we can do like this ..
suppose there are two lists
1->2->3->4->5
5->6->7
take two variables num1 and num2
traverse first list

node *n=h1; //h1 is head of first list
int num1=0;
while(n->next!=null)
num1 = num1*10 + n->val;

so num1 is the no. represented by the first list ..
similarly we can find num2 for the 2nd list and add them to get sum

complexity is O(m+n)
where m and n are size of the first and 2nd list respectively