Amazon Qualcomm Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
12
of 12 vote

Following code is tested. It handles the case where first list is longer than the second, or second is longer than the first as well as when they are of equal length.

int FindLength(Node* n) { // find the length of a given linked list.
	int ret = 0;
	while(n) {
		ret++;
		n = n->next;
	}
	return ret;
}
Node* Add(Node* list1, Node* list2) { // this function is called first
	int state = FindLength(list1) - FindLength(list2);
        // if state > 0, list1 is longer
        // if state < 0, list2 is longer
        // if state == 0, list1 and list2 is of same length
	int carry = 0;
	Node* ret = Add2(list1, list2, carry, state); // add the two lists	
	if ( carry > 0 ) { // handle carry for the leftmost digit
		Node* temp = new Node(carry);
		temp->next = ret;
		ret = temp;
	}
	return ret;
}
Node* Add2(Node* p1, Node* p2, int& carry, int state) { // helper function
	if ( p1 == NULL && p2 == NULL ) // if both are NULL, we are at the end
		return NULL;
	Node* ret = new Node(0); // create new node to return
	if ( state > 0 ) { // p1 is still longer than p2
                // only advance p1's pointer and decrease state
		ret->next = Add2(p1->next, p2, carry, state-1);
		ret->data = carry + p1->data; // just sum carry and p1's data
	}
	else if ( state < 0 ) { // p2 is still longer than p1
                // only advance p2's pointer and increase state
		ret->next = Add2(p1, p2->next, carry, state+1);
		ret->data = carry + p2->data; // just sum carry and p2's data.
	}
	else { // p1 and p2 are of same length
                // advance both pointers, state should stay untouched from now on(0).
		ret->next = Add2(p1->next, p2->next, carry, 0);
		ret->data = carry + p1->data + p2->data; // sum carry and both digits
	}
	carry = ret->data / 10; // calculate new carry
	ret->data %= 10;        // update the current data to be smaller than 10
	return ret;             // return the new node

}

- crdmp December 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

using recursion here is an overkill (also giving that the lists can be of arbitrary length). can be done within a single loop

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is fine did you handled 8888889 and 111

- Sanjay Kumar December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tested it when I saw your comment. The code returned the correct result.

- crdmp December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

english please? What is your approach?

- sushant.singh1987 January 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I first find the difference in length of both linked lists and save this value in a variable called state. If state is positive, the first list is longer, if it's negative, the second list is longer and if it's 0, their lengths are equal.


To handle the carry properly, and to handle the difference in length, we need to do the addition starting from the end of the lists. So, I wrote a recursive function (Add2) that gets the then current head of the linked lists, a reference to int to pass the carry, and the value of the state variable. As long as the state variable is nonzero, we know that the two linked lists this function gets are not equal in length. That's why if the state variable is positive, we only add the value from the first linked list and if the state variable is negative, we only add the value from the second linked list.


The critical part happens here. Note that we only advance the pointer of the longer linked list while recursively calling Add2 at this point. The other important part is updating the state variable for the next call. We either increment or decrement the state value (whichever brings it closer to 0).


Only if they are equal in length, we add both of them and advance both pointers for the next call of Add2.


After we do the additions, we update the value of that node to be less than 10, and calculate the new carry. Since the carry variable is a reference, we can successfully pass this value to the previous call of our function. At the end, Add2 returns the head of the then current result. Inside Add, we also need to take care of the carry for cases where the result has more digits than both the first linked list and second linked list (e.g: 999+1). So if the carry is greater than 0, we create another node and put that node at the head of the resulting list.

- crdmp January 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Since you have calculated the lengths,
move the longer list's head by (|l1-l2|) nodes, and then just handle the case of equal lengths with carry at the head of longer list
...
it will save some un wanted code

- Ashupriya July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

In interviews like that of Amazon, please don't expect the interviewer to give the expected complexity, etc. They want us to give an optimal solution. Gone are the days of merely solving problems. This is the time of scalability. So better make ur solutions how-much-ever optimal in the first go itself. My own experience with Amazon, I had high hopes, but they said, my problem solving skills are bad, though i gave all solutions. But not optimal ones.

- Anonymous November 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

There could be multiple approaches. Two of them are listed below:
Approach 1: Convert the linked lists to numbers. Add them. And then convert back the resultant number to a linked list.
Approach 2: Take two stacks and push a linked list to a stack. After done pushing, simply start popping the stacks, add the numbers, get the carry over, generate another node with the result and add to front to a new linked list.
I prefer the second approach as this is less prone to errors while coding and faster when in-built library functions for stacks are used, although it takes memory with order of m+n where m and n are lengths of the linked lists.

- Victor December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1)I don't think they would allow you to do that. If you were to add numbers, he would have given the numbers.
2)Stacks is more like reversing the linked list and then adding them up. He asked to avoid reversing the linked list.

- manjunath426jc December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

what is this ? "practice coding question for dummies ?" ))

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The first approach might lead to overflow if the list is too huge such that the sum of its elements is beyond the range of int/long.

The second approach is the only one that looks achievable. we can do something like this:

1. find the length of 2 lists => len_l1 and len_l2(lets say len_l1 > len_l2)
2. traverse the bigger list skipping (len_l1 - len_l2) nodes in l1.

3. now keep pushing teh current top of each list into the stack and call step 3 recursively passing (l1->next, l2->next).

4. in the recursive method implementing step 3, check if(nodeFromListOne->next == NULL && nodeFromListTwo->next == NULL). if so, this is the last node and we must start returning (popping from stack) after this instead of contuining with recusrion.

5. return the sum of digitList1 and digitList2 as well as the carryover value.

6. in the caller stack (to whom these values are returned), use the carry over value returned for summation again. also to store the sum, we can either create a new list or update either list1 or list 2 with the sum

- Jester December 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if input is like more than 9000000000000000000 u should not have data type to store this as number

- kalai July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

manjunath426jc:
The difference between the recursive solution by 'crdmp' and the 2nd approach of 'Victor' is that in recursive solution, the system(language-library and/or OS) will maintain a stack where as in 'Victor' case the program will explicitly maintain a stack.

To me none of them are reversing the list and using explicit stack is always better than a recursive solution since system's method stack consumes more memory and cause performance overhead than explicit stack maintenance.

In fact my vote goes to Victor's 2nd approach.

- buckCherry November 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

/*Solution Code to algorithm suggested by lanse.cse
		1. reverse the lists. 
		2. add them digit by digit and construct the result list. 
		3. reverse the result list.
	NOTE: This code demonstrates the solution. The code will fail for invalid or no input and maybe other cases. Output for the following code : 9,1,3,1,3,8
*/
#include <iostream>
using namespace std;
//! Node to store digits
struct Node{
	short digit;	//doesn't make a difference if I use short or int
	Node* next;
};
//!Function reverses an input list
void reverseList(Node*& head){
	Node* curr = head;
	Node* nxt  = head->next;
	curr->next = NULL;
	while(true){
			head	   = nxt;
			if(head->next==NULL){
				head->next = curr;
				break;
			}
			nxt	   = nxt->next;
			head->next = curr;
			curr	   = head;
	}
}
//! Function to compute the sum of two input lists. Complexity: O(m+n), sizes of lists m,n
void sumOfLists(Node*& list1, Node*& list2, Node*& result){
	// Reverse lists: Time: O( m + n). operating on input lists to save space complexity
	reverseList(list1);
	reverseList(list2);
	Node* ptr;
	ptr = new Node();
	result = ptr;
	int n1=0,n2=0,sum=0,carry=0;
	bool n1flag=true,n2flag=true;
	while(n1flag || n2flag){
		n1= n1flag?list1->digit:0;
		n2 = n2flag?list2->digit:0;
		sum = n1+n2+carry;
		carry = (sum>=10)?1:0;
		ptr->digit = (sum-10*carry);
		if(n1flag)
			if(list1->next==NULL)
				n1flag = false;
			else
				list1 = list1->next;
 		if(n2flag)
			if(list2->next==NULL)
		 		n2flag = false;
			else
				list2 = list2->next;
		if(n1flag || n2flag){
			ptr->next = new Node();
			ptr = ptr->next;
		}else
			ptr->next = NULL;
	}
	reverseList(result);
}
void printListValues(Node*& list){
	Node* ptr=list;
	do{
		cout<<ptr->digit<<",";
		ptr = ptr->next;
	}while(ptr->next!=NULL);
	cout<<ptr->digit<<endl;
}
int main(){
	
	//construct two lists, replace the below digits to test your values
	int myNum1[] = {9,1,2,3,2,9};//First list 912329,
	int myNum2[] = {0,8,0,9};  //second list 0809
	Node *newNd1, *num1, *num2, *result;
	newNd1=new Node;num1 = newNd1;
	int sz = sizeof(myNum1) / sizeof(int);
	for(int i=0;i<sz;++i){
		newNd1->next = (i==sz-1)?NULL:(new Node);
		newNd1->digit = myNum1[i];
		newNd1=newNd1->next;
	}
	newNd1 = new Node;num2 = newNd1;
	sz = sizeof(myNum2) / sizeof(int);
	for(int i=0;i<sz;++i){
		newNd1->digit = myNum2[i];
		newNd1->next = (i==sz-1)?NULL:(new Node);
		newNd1=newNd1->next;
	}
	//Find sum
	sumOfLists(num1,num2,result);	//. Result should be 913138
 	printListValues(result);
}

- chennavarri November 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

how abt this idea?
first we will fetch the lengths. then we will add 0's in the heads place of smaller linkedlist till the lingth of both becomes same..
lets assume linked list numbers are 999 and 999
the heads 99(this 9,9 are both the heads of two linked lists) will become 18. we will keep 18 . bein in the same place , we will calculate , the next's su, if there is carry , we will increment , the currnt number.then we will move to next. will repeat the same while ->next != null.

- gopi December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about for the case 909 + 999 ?

- Hulk February 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

hw abt using stack n push n pop n add

- Anonymous November 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can use but that would add O(n) space to the complexity. It's better to use the concept of reversing singly link list.

@Others: suggest any other better solution.

- Jit November 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a feeling that the question is not complete. because here's a bruteforce O(n) solution.

Assume 'n' elements in each linked list, 
  construct an array from each linked list, 
  start from the end of the arrays and keep adding elements and storing into another array with carry. The max size of the second array can be 2n.
  Build another linked list from the result array.
  Time complexity: O(n + n + 2n + 2n) => O(6n) => O(n)
  Space complexity: O(n + n + 2n) => O(4n) => O(n)

so what are we trying to optimize? space , time ? or something else?

- chennavarri November 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Question is incomplete as it doesn't give any constrain, though reversing the list sounds like a better solution. Anyways you can tell both the solutions and let the interviewer choose.

- JoshMachine November 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

So can we just process the linked lists and get the number? I.e. multiply by 10 for each -> next. Or are we assuming the numbers are just too big to fit in a long?

- anon November 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is possible that the number could be 1000 digits, until now we dont have any standard datatype that stores 1000 digits. so consider we are building a new datatype which can add astronomical numbers

- blue_skin November 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I mentioned the pushing into stack answer. But interviewer was not happy.

How does reversing link list work?

- Interview November 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

lets say the numbers are 1->2->3 and 1->2
After reversing the lists look like 3->2->1 and 2->1
Now add the two lists node by node and properly take care of the carry over of the addition of the nodes, if any.
so, the resultant added list will look like 5->3->1
Now reverse the "resultant added list" to get the result of addition of two original lists. That is 1->3->5 is the actual answer.

- Jit November 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For addition, instead of reversing the link list, shouldn't we make the exact no by traversing through the list. because if we reverse the link list we are changing the input also.
And building the exact number is easier than reversing the link list.

take your example itself.
1->2->3.
no will be= (1*10+2)*10+3=123
1->2
no will be= 1*10+2=12

now add the nos= 123+12=135.

Store the resulting number in Link list. that can be done in reverse order. (because we will do divide by 10).
then reverse this Link List.

In this approach we don't have to worry about carry over also.

Please suggest.

- ashpiy November 09, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ashpiy, how would handle the number if it exceeds the integer range..how would you store the numbers before addition and the result after addition..?

- Jit November 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, that's correct. I did not think about the carry.

- Piyush Beli March 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I did not think about that.

- Piyush Beli March 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys, there is some amount of repeated code. Any optimized version would be highly appreciated..
Please suggest any other better approach..
Time Complexity is O(n).

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

struct Number
{
	int key;
	struct Number* next;
};

typedef struct Number node;

void createDigits(node **);
void printDigits(node *);
void reverseDigits(node **);
void addDigits(node *, node *, node **);

int main()
{
	node* head1 = NULL;
	node* head2 = NULL;
	node* head3 = NULL;
	
	printf("Create the first number..\n");
	createDigits(&head1);
	if(head1 == NULL)
	{
		printf("First Input is not correct..\n");
		return 1;
	}
	printf("Create the second number..\n");
	createDigits(&head2);
	if(head2 == NULL)
	{
		printf("Second Input is not correct..\n");
		return 1;
	}
	printf("Number 1: \n");
	printDigits(head1);
	printf("\n");
	printf("Number 2: \n");
	printDigits(head2);
	printf("\n");
	printf("Number 1 reversed..\n");
	reverseDigits(&head1);
	printDigits(head1);
	printf("\n");
	printf("Number 2 reversed..\n");
	reverseDigits(&head2);
	printDigits(head2);
	printf("\n");
	printf("Add the two reversed numbers node by node..\n");
	addDigits(head1, head2, &head3);
	printf("Reversing the result to get the actual result..\n");
	reverseDigits(&head3);
	printf("sum of two numbers in linked representation is: \n");
	printDigits(head3);
	printf("\n");
	return 0;
}

void createDigits(node **list)
{
	int digit = 0;
	node* tNode = NULL;
	printf("Enter positive digits to insert..(enter -999 to exit)\n");
	scanf("%d",&digit);
	if(digit == -999)
	{
		printf("Input completed..\n");
	}
	else
	{
		if(NULL == *list)
		{
			*list = (node *)malloc(sizeof(node));
			(*list)->key = digit;
			(*list)->next = NULL;
			createDigits(list);
		}
		else
		{
			tNode = *list;
			while(tNode->next != NULL)
				tNode = tNode->next;
			tNode->next = (node *)malloc(sizeof(node));
			tNode = tNode->next;
			tNode->key = digit;
			tNode->next = NULL;
			createDigits(list);
		}
	}
}

void printDigits(node* list)
{
	if(list->next != NULL)
	{
		printf("%d->",list->key);
		printDigits(list->next);
	}
	else if(list->next == NULL && list->key != -999)
	{
		printf("%d\n",list->key);
	}
	else 
	{
		printf("Empty List..\n");
	}
}

void reverseDigits(node** list)
{
	node* temp1 = *list;
	node* temp2 = NULL;
	node* temp3 = NULL;

	while(temp1)
	{
		*list = temp1;
		temp2 = temp1->next;
		temp1->next = temp3;
		temp3 = temp1;
		temp1 = temp2;
	}
	//return *list;
}

void addDigits(node* head1, node* head2, node** head3)
{
	node* temp = NULL;
	int keyVal = 0;
	static int pass = 0;
	if(head1 != NULL && head2 != NULL)
	{
		keyVal = head1->key + head2->key + pass;
		if(*head3 == NULL)
		{
			*head3 = (node *)malloc(sizeof(node));
			if(*head3 == NULL)
			{
				printf("Memory Allocation Failed..\n");
			}
			if(keyVal >= 10)
			{
				(*head3)->key = keyVal-10;
				pass = 1;
			}
			else
			{
				(*head3)->key = keyVal;
				pass = 0;
			}
			(*head3)->next = NULL;			
		}
		else
		{
			temp = *head3;
			while(temp->next != NULL)
				temp = temp->next;
			temp->next = (node *)malloc(sizeof(node));
			if(temp->next == NULL)
			{
				printf("Memory Allocation Failed..\n");
			}
			temp = temp->next;
			if(keyVal >= 10)
			{
				temp->key = keyVal-10;
				pass = 1;
			}
			else
			{
				temp->key = keyVal;
				pass = 0;
			} 
			temp->next = NULL;
		}
		head1 = head1->next;
		head2 = head2->next;
		addDigits(head1, head2, head3);
	}
	else if(head1 == NULL && head2 != NULL)
	{
		keyVal = head2->key + pass;
		if(*head3 == NULL)
		{
			*head3 = (node *)malloc(sizeof(node));
			if(*head3 == NULL)
			{
				printf("Memory Allocation Failed..\n");
			}
			if(keyVal >= 10)
			{
				(*head3)->key = keyVal-10;
				pass = 1;
			}
			else
			{
				(*head3)->key = keyVal;
				pass = 0;
			}
			(*head3)->next = NULL;			
		}
		else
		{
			temp = *head3;
			while(temp->next != NULL)
				temp = temp->next;
			temp->next = (node *)malloc(sizeof(node));
			if(temp->next == NULL)
			{
				printf("Memory Allocation Failed..\n");
			}
			temp = temp->next;
			if(keyVal >= 10)
			{
				temp->key = keyVal%10;
				pass = 1;
			}
			else
			{
				temp->key = keyVal;
				pass = 0;
			} 
			temp->next = NULL;
		}
		head2 = head2->next;
		addDigits(head1, head2, head3);
	}
	else if(head1 != NULL && head2 == NULL)
	{
		keyVal = head1->key + pass;
		if(*head3 == NULL)
		{
			*head3 = (node *)malloc(sizeof(node));
			if(*head3 == NULL)
			{
				printf("Memory Allocation Failed..\n");
			}
			if(keyVal >= 10)
			{
				(*head3)->key = keyVal-10;
				pass = 1;
			}
			else
			{
				(*head3)->key = keyVal;
				pass = 0;
			}
			(*head3)->next = NULL;			
		}
		else
		{
			temp = *head3;
			while(temp->next != NULL)
				temp = temp->next;
			temp->next = (node *)malloc(sizeof(node));
			if(temp->next == NULL)
			{
				printf("Memory Allocation Failed..\n");
			}
			temp = temp->next;
			if(keyVal >= 10)
			{
				temp->key = keyVal-10;
				pass = 1;
			}
			else
			{
				temp->key = keyVal;
				pass = 0;
			} 
			temp->next = NULL;
		}
		head1 = head1->next;
		addDigits(head1, head2, head3);
	}
	else if(pass == 1)
	{
		temp = *head3;
		while(temp->next != NULL)
			temp = temp->next;
		temp->next = (node *)malloc(sizeof(node));
		if(temp->next == NULL)
		{
			printf("Memory Allocation Failed..\n");
		}
		temp = temp->next;
		temp->key = pass;
		temp->next = NULL;
	}
}

- Jit November 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it looks very big code. I would still suggest not to do reverse link list.

- Piyush November 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about:
sum = atoi(list1) + atoi(list2)
where atoi is modified version that operates on list of numbers.
Then, itoa(sum), which ouputs as a list of numbers.

- Anonymous November 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks fine for small numbers, how about large numbers that exceed integer ranges..

- Jit November 09, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the following rephrase of th equestion correct (rephrased/introduced words in quotes):

You have two "set" of numbers represented by "two" linked lists, where each node contains a single digit. Write a function that adds the two numbers "in the corresponding nodes" and returns the sum as a "third" linked list

- Anonymous November 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the different solution than others, and looks better also.

- Piyush Beli March 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

By reversing LinkList is very lengthy.

We have two Linklist A and B of length x and y(we can find length by simple traversing)

Now There may be three condition:(x=y,x>y,x<y):
_____________________________________________________________________________________
[1]:length of list A and length of List B are same (x=y):
In this case we can use simple recursion which will start from the end of list and proceed to front.recursive function will return carry digit(1 OR 0).
**********
+
**********
=
**********
NOTE: '*' can be any digit (0-9)
____________________________________________________________________________________
[2]:if length of List A is greater then length of list B(x>y):
In this case we will divide our bigger link list into two part (A1 and A2).First part(A1) will be of length (x-y) and second part(A2) will be of length (y). Now second part(A2) of List A and B are of same length (y).we can add it by simple recursion as we did in condition [1].After adding these two (A2 and B) we will append first part(A1) of list A if there is not carry digit in (A2+B).If there is any carry digit in (A2+B) we will apply recursion this time in first part(A1)of A
and add one at the end of A1 and then appent the modified A'1 with (A2+B).We will get A'1(A2+B).The resultent sum.
*******************(x) *******A1(x-y) ************A2(y)
+ + ************B(y)
**********(y)
= *******A1(x-y) ************[A2+B](y)
=
*****************(x) = *****************[A1][A2+B](x)

___________________________________________________________________________________
[3]:if length of List A is lesser then length of list B(x<y):
Same as condition [2] by replacing x with y.

Recursive Function:

int addTwoList(node *A,node *B)
{
int i=0;;
if(A->link!=NULL)
{
A=A->link;
B=B->link;
i=addTwoList(node *A,node *B);
}
A->info=A->info+B->info+i;//assigning addition into A.(A=A+B).
if(A->info>9)
{
i=1;
}
return i;
}

__________________________________________________________________________________

- PKT January 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

*******A1(x-y) ************A2(y)
+ ---------------************B(y)

= *******A1(x-y) ************[A2+B](y)
= *****************[A1][A2+B](x)

- PKT January 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello PKT
I feel a lil problem there!!! If u r adding the lists from end are u assuming them to be pointing to their prev. node??
Otherwise u need to use linked List reversal!!

- Neal February 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple solution. Complexity - O(n)

int carry = 0;
while(nodenum1->next!=null or nodenum2->next!=null)
{
addition = carry + nodenum1->data + nodenum2->data;
carry = (nodenum2->data)/ 10;
nodenum2->data = addition - (carry*10)
}

reverse(nodenum2)

- O(1) February 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

***Ignore the above solutions***

Simple solution. Complexity - O(n)

reverse(linkedlist_of_Num1)
reverse(linkedlist_of_Num2)

int carry = 0;
while(nodenum1->next!=null or nodenum2->next!=null)
{
addition = carry + nodenum1->data + nodenum2->data;
carry = (nodenum2->data)/ 10;
nodenum2->data = addition - (carry*10)
}

//Copy the remaining elements of larger list in the nodenum2

//reverse the resultant
reverse(nodenum2)

- O(1) February 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why all you guys checking (nodenum1->next!=null or nodenum2->next!=null) only. What if both lists end but there is still carry to consider. Here is simple test case.

list1 contains single element 5 and list2 contains any element >5

- Anonymous February 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys Here is a solution without reversing the link lists
Time Complexity = O(n)
Works for any length of linked lists

l1 = length_linklist(head1);
    l2 = length_linklist(head2);
    while(l1<l2){
        temp = create_node(0);
        temp->next = head1;
        head1 = temp;
        l1++;
    }
    while(l2<l1){
        temp = create_node(0);
        temp->next = head2;
        head2 = temp;
        l2++;
    }  
    add(head1,head2);

My add function

void add(node *head1,node *head2){
    if(head1!=NULL){
        add(head1->next,head2->next);
        int sum = head1->val+head2->val;
        head1->val = sum%10+carry;
        carry = sum/10;
    }
}

- Anonymous June 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

since you are adding 1 digit numbers you can skip % and use sum - 10, it's much faster.

Also notice that curry=sum/10 is always 0 as it's a int/int = int

- N568 January 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys Here is a solution without reversing the link lists
Time Complexity = O(n)
Works for any length of linked lists

l1 = length_linklist(head1);
    l2 = length_linklist(head2);
    while(l1<l2){
        temp = create_node(0);
        temp->next = head1;
        head1 = temp;
        l1++;
    }
    while(l2<l1){
        temp = create_node(0);
        temp->next = head2;
        head2 = temp;
        l2++;
    }  
    add(head1,head2);

My add function

void add(node *head1,node *head2){
    if(head1!=NULL){
        add(head1->next,head2->next);
        int sum = head1->val+head2->val;
        head1->val = sum%10+carry;
        carry = sum/10;
    }
}

- TheCoder June 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can perform this, by traversing the two lists and getting the two numbers. Then adding the two numbers through simple int addition and saving the result in another link list.

a. getting int
while( a != NULL)
num = num*10 + a->value;

num_final = num1+num2

get digits of final and save it in another list.

- Srikant Aggarwal November 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

The following 'sum' method will return the requirement .

private static int sum(LinkedList l1, LinkedList l2) {
        int sum = 0;
        int decimal = 1;
        int max = 0, min = 0;
        if (l1.size() > l2.size()) {
            max = l1.size() - 1;
            min = l2.size() - 1;
        } else {
            max = l2.size() - 1;
            min = l1.size() - 1;
        }
        for (int i = max; i >= 0; i--) {
            if ((l1.size() - 1) == max) {
                sum = sum + (decimal * (Integer) (l1.get(i)));
            } else {
                if (min >= 0) {
                    sum = sum + (decimal * (Integer) (l1.get(min)));
                    min--;
                }
            }
            if ((l2.size() - 1) == max) {
                sum = sum + (decimal * (Integer) (l2.get(i)));
            } else {
                if (min >= 0) {
                    sum = sum + (decimal * (Integer) (l2.get(min)));
                    min--;
                }
            }
            decimal = decimal * 10;
        }
        return sum;
    }

AnanthaNag KUNDANALA

- AnanthaNag KUNDANALA December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but lists can be of arbitrary length thus you can get an overflow in 'sum'

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Overflow ???

will you please give me an example ?

- AnanthaNag KUNDANALA December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

point is you accumulate your resulting sum in an integer (not in a list) consider adding two very long lists like

1->1->1->1-> ... ->1->1

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

got you. So, I guess replacing 'int' with some other bigger primitive datatype (like long), I will be in safe side. Is n't it ?

- AnanthaNag KUNDANALA December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

well, probably this stuff should be clarified with an interviewer:
this also shows that you are aware of the problem..
if the lists contain thousands of nodes, any standard number type would give an overflow, thus the general solution is to use a list for the resulting sum as well

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yup. thanks a ton for enlightenment. Till now, I never thought of overflow of additions & other mathematical operations with respect to the range of the primitive datatypes. Thanks once again.

- AnanthaNag KUNDANALA December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And may I have you in my mail contacts list? If you have no issues to be in my contacts, please revert me at kundanala@gmail.com

- AnanthaNag KUNDANALA December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Kundan I need second idea on my algo also.. Please comment.

- Sanjay Kumar December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

let me try this...
start parsing both the link list one node at a time.. to find out which is the largest one and what is the diff in the length..
suppose list1 1->2->3->4
and list2 5->3->4->6->9->2->1
given example L1=4 L2=7 and diff=3

create a function like below..

it can be passed to function

Node* add_node(Node *N1,Node *N2,size)
{
static int carry;
int sum,remainder;
Node *temp_node;

if(N1==NULL || N2==NULL)
return NULL;

if(size<=diff)
{
size++;
temp_node=(Node*)malloc(sideof(Node*));
temp_node->next=add_node(N1,N2->next,size);
sum=N2->value+carry;
}
else
{
size++;
temp_node=(Node*)malloc(sideof(Node*));
temp_node->next=add_node(N1->next,N2->next,size);
sum=N1->value+N2->value+carry;
}

carry=sum/10;
remainder=sum%10;

temp_node->value=remainder;
return temp_node;
}

tere might more exception handling and we need to take care.. but this is my over all idea..

- Sanjay Kumar December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct list_t{ 
	int x;
	struct list_t* next;
	} list_t;
	
    
// add two lists and return a list
list_t* add(list_t* A, list_t *B){  
	int s;
	list_t* least=NULL; //pointer to the sum list least impotant digit
	list_t* most=NULL; //pointer to the sum list most impotant digit
	list_t* tmp=NULL;	
	               
	// while there are 2 digits, add them
	while( A != NULL && B != NULL){
		s = A->x + B->x;           
		// initialize sum list
		tmp = malloc(sizeof(list_t));
		if(least == NULL){
			least = most = tmp;
		}
		// add either 1 or 2 digits
		if(s<9){
			tmp->x = s;
			tmp->next = NULL;
			most->next=tmp;
			most=tmp;
		   }
		else{
			tmp->x = s -10;
			tmp->next = malloc(sizeof(list_t));
			tmp->next->x = 1;
			tmp->next->next=NULL;
			most->next=tmp;
			most=tmp->next;			
		}       	 
		A=A->next;   		
		B=B->next;
	}               
	while( A != NULL ){	
		most->next=malloc(sizeof(list_t));
		most->next->x = A->x;
		A = A->next;         
		most = most->next;		
	}
	while( B != NULL ){	
		most->next=malloc(sizeof(list_t));
		most->next->x = A->x;
		B = B->next;         
		most = most->next;		
	}
	return least;
}

- N568 January 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(9);
ll.add(9);
ll.add(9);
LinkedList<Integer> ll1 = new LinkedList<Integer>();
ll1.add(9);
ll1.add(9);
ll1.add(9);
ll1.add(5);
int num1 = 0;
int num2 = 0;
for(int i =ll1.size()-1 ; i>=0;i-- ){
 int temp = ll1.get(i);
	for(int j =0;j<i;j++){
		temp=temp*10;	
	}
		num1=num1+temp;
}
System.out.println(num1);

for(int i =ll.size()-1 ; i>=0;i-- ){
	 int temp = ll1.get(i);
		for(int j =0;j<i;j++){
			temp=temp*10;	
		}
			num2=num2+temp;
	}
	System.out.println(num2);
	
	System.out.println("num1+num2 = "+(num1+num2));

This should do!!

- Ravi January 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int FormNumber( Node *n )
{
        if( n == NULL )
                return 0;
        static int sum = 0 , i =0;
        FormNumber( n->next );
        sum = sum + (n->data)* pow( 10 , i );
        i++;
        return sum;
}



int Add( Node *h1 , Node *h2 )
{

        return FormNumber(h1) + FormNumber(h2 );
}

- Sasi February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int FormNumber( Node *n )
{
if( n == NULL )
return 0;
static int sum = 0 , i =0;
FormNumber( n->next );
sum = sum + (n->data)* pow( 10 , i );
i++;
return sum;
}



int Add( Node *h1 , Node *h2 )
{

return FormNumber(h1) + FormNumber(h2 );
}

- Sasi February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Sum 2 lists
struct node* sum2LL(struct node* head1, struct node* head2)
{
	struct node* head = NULL;
	struct node* headcopy = head1;
	int carry = 0, sum = 0;
	
	if(head1 == NULL && head2 == NULL)
		return NULL;
	else if(head1 == NULL && head2 != NULL)
		return head2;
	else if(head1 != NULL && head2 == NULL)
		return head1;
	else
	{
		// Both list have elements
		while(head1 != NULL && head2 != NULL)
		{
			printf("head1->data : %d head2->data : %d Carry : %d\n", head1->data, head2->data, carry);
			sum = head1->data + head2->data + carry;
			if(sum > 9)
			{
				carry = (sum % 10) + 1 ;
				printf("Sum : %d Carry : %d\n", sum, carry);
				sum = sum - carry;
			}else
				carry = 0;
			printf("Sum : %d Carry : %d\n", sum, carry);
			
			// First node
			if(headcopy == head1)
				head = createNode(sum);
			else
				addTail(&head, sum);
			
			head1 = head1->next;
			head2 = head2->next;
		}
		
		// Both of them are empty
		if(head1 == NULL && head2 == NULL)
		{
			if(carry == 0)
				return head;
			else
			{
				addTail(&head, carry);
				return head;
			}
		}
		//Only Head1 is empty
		else if(head1 == NULL && head2 != NULL)
		{
			if(carry == 0)
			{
				struct node* tail = findTail(head);
				tail->next = head2;
			}
			else
			{
				while(head2 != NULL)
				{
					sum = head2->data + carry;
					if(sum > 9)
					{
						carry = (sum % 10) + 1 ;
						sum = sum - carry;
					}
					else 
						carry = 0;
					
					addTail(&head, sum);
					
					head2 = head2->next;
				}
			}
			return head;
		}
		// Only head2 is NULL
		else if(head1 != NULL && head2 == NULL)
		{
			if(carry == 0)
			{
				struct node* tail = findTail(head);
				tail->next = head1;
			}
			else
			{
				while(head1 != NULL)
				{
					sum = head1->data + carry;
					if(sum > 9)
					{
						carry = (sum % 10) + 1 ;
						sum = sum - carry;
					}
					else 
						carry = 0;
					
					addTail(&head, sum);
					
					head1 = head1->next;
				}
			}
			return head;
		}
	}
}

- Candida June 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hope this solution will also work.
step 1: Calculate the length of both LinkList , say L1 and L2
step 2: Calculate the difference d, and find out which is longer.
step 3: Traverse the longer List for 'd' number of nodes.
step 4: Now start adding the nodes value of both LinkList and keep the Sum in longer List L1.
step 5: This way longer List L1 will have the its own starting number and Sum of each digit.
step 6: Finally create a function which have 'carry' as Static variable and traverse from end of a linklist using recursion. Use mod function to get the 'carry' part of each node starting from the end. And add this carry to previous node(in recursion). this way carry will propagate in backward direction.
step 7: If the carry still have some value when we come to first node then create a new node and add to the starting of the Linklist.

What say Guys..?

- apandey846 July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse both the list, soppose l1 = 1->2->9 and l2= 8->9
so l1 = 9->2->1 and l2 = 9-> 8
add the first elements of both list 9 + 9 = 18 put it in the stack
add second element until all the elements are empty and put it in the queue so queue become
18, 10,1
then dequeue up element if greater than 10, then remove 10 and add 1 for the next element
so it become 8, (10+1) = 11-10 =1 , 1+1 = 2 and then put it a new list become 8->1->2
now reverse the list = 2->1->8
hope this is clear

- Anonymous October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

With the reversing->adding->reversing we need 5 iterations (i.e., revering two list, adding two list and reversing the resultant list).

Instead why not add the lists in the forward direction creating add-list and carry-list, then add the add-list and carry-list to get the final list. (Note: we need to iterate both the list to find the respective lengths first).

lets try this way Sum: 9999 + 9999
Add-list is 088888 and the carry list is 111110 and adding this list will give us 199998.

Complicity is 4 iterations (2 iterations to identify the length of the lists and 2 iterations for adding).

- Kireeti Kanumolu November 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my tail recursive version, which doesn't require first finding the lengths, first reversing, converting the lists to numbers, or using additional data structures such as Stack etc. It won't handle the case of overflow, so I might be solving an easier version of this problem.

The approach is to use 2 additional parameters (num & num2) to keep track of the current values we have seen for both lists. Code should be self-explanatory enough...

static int sum(Node n, Node n2, int num, int num2) {
	if(n == null && n2 == null)
		return num+num2;
	else if(n == null)
		return sum(null, n2.next, num, 10*num2 + n2.value);
	else if(n2 == null)
		return sum(n.next, null, 10*num + n.value, num2);
	else return sum(n.next, n2.next, 10*num + n.value, 10*num2 + n2.value);
}

- Sunny December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
A recursive approach without modifying the linked list. {{{ insertintoAddList(int k1) { struct node *l=malloc(sizeof(struct node)); l->val=k1; l->next=NULL; if(head3==NULL) head3=l; else { l->next=head3; head3=l; } } //h1 = head of smaller list h2=kth node of bigger list where k-1 is difference between two list void Add2LinkedList(struct node* h1, struct node *h2) { static int k=0; if(h1==NULL && h2==NULL) return; Add2LinkedList(h1->next,h2->next); if(h1->val+h2->val>9) { insertintoAddList(h1->val+h2->val-10+k); k=1; } else { insertintoAddList(h1->val+h2->val+k); k=0; } } void AddRemaining(struct node *h) // head of bigger list { static int k1=0; if(h!=h2) AddRemaining(h1->next); if(head3->val>9) k1=1; else k1=0; insertintoAddList(h->val+key); } - Shashi January 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int addLists (node* list1, node* list2)
{
int add1=0, add2=0, final=0;
while (list1->next != NULL && list2->next!= NULL)
{
add1 = add1*10 + list1->value;
add2 = add2*10 + list2 -> value;
if(list1->next != NULL) list1 = list1->next;
else final += add1;
if(list2->next != NULL) list2 = list2->next;
else final += add2;
}

return final;
}

- Erick April 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be solved using stack.
Step1: Insert all the elements in the list1 into a stack say s1
Step2: Insert all the elements in the list2 into a stack say s2
Step3:
int val1,val2,carry=0;
while(!s1.empty() || !s2.empty())
{
val1=0;
val2=0;
if(!s1.empty())
{
val1=s1.top();
s1.pop();
}
if(!s2.empty())
{
val2=s2.top();
s2.pop();
}
if(val1+val2+carry> 10)
{
carry=1;
insertintoll((val1+val2+carry)-10);
}
else
{
carry=0;
insertintoll((val1+val2+carry));
}
}

Note: insertintoll() function inserts the value to the front of the new linked list

- vigneshb06 July 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My Generation

- triple H February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the code from k2code.blogspot.in/2009/12/write-program-to-add-two-long-positive.html:

node *long_add(mynode *h1, mynode *h2, mynode *h3)    //h3 = h2+h1
{
  node *c, *c1, *c2;
  int sum, carry, digit;
 
  carry = 0;
  c1 = h1->next;
  c2 = h2->next;
 
  while(c1 != h1 && c2 != h2)
  {
     sum   = c1->value + c2->value + carry;
     digit = sum % 10;
     carry = sum / 10;
 
     h3 = insertNode(digit, h3);
 
     c1 = c1->next;
     c2 = c2->next;
  }
 
  if(c1 != h1)
  {
     c = c1;
     h = h1;
  }
  else
  {
     c = c2;
     h = h2;
  }
 
  while(c != h)
  {
    sum   = c->value + carry;
    digit = sum % 10;
    carry = sum / 10;
    h3 = insertNode(digit, h3);
    c = c->next;
  }
 
  if(carry==1)
  {
     h3 = insertNode(carry, h3);
  }
 
  return(h3);
}

- kinshuk.ram May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static LinkedList listSum(LinkedList num1, LinkedList num2){
Deque<Integer> n1St = new ArrayDeque<Integer>();
Deque<Integer> n2St = new ArrayDeque<Integer>();
//Stack<Integer> st = new Stack<Integer>(); We resort to using ArrayDeque as it is faster than Stack
//Why is ArrayDeque faster than Stack ?
//ArrayDeque is extended from ArrayList whereas Stack is from Vector
//ArrayList is not a synchronized call & hence when we are not working with multi-threaded program, why
//take a perfromance hit by using vector, i.e., Stack

LinkedList t = num1;
while(t != null){
n1St.push(t.val);
t = t.next;
}

t = num2;
while(t != null){
n2St.push(t.val);
t = t.next;
}

int carry = 0;
int sum = 0;
LinkedList nd = new LinkedList();
nd.val = 0;
nd.next = null;
LinkedList head = nd;
LinkedList next = null;
while (!n1St.isEmpty() || !n2St.isEmpty() || (carry != 0)){
if (!n1St.isEmpty())
sum += n1St.pop();
if (!n2St.isEmpty())
sum += n2St.pop();
sum += carry;
carry = sum / 10;
sum = sum % 10;

if (next == null){
next = nd;
} else {
nd = new LinkedList();
nd.next = next;
next = nd;
}
head = nd;
nd.val = sum;
sum = 0;
}

return head;
}

- Anonymous October 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simpler recursive implementation:

private static LinkedList<int> AddNumbers(LinkedListNode<int> firstNumNode, LinkedListNode<int> secondNumNode,int carry)
	{
		//Base Case:
		if(null == firstNumNode && null == secondNumNode)
		{
			//If we have done with the list but we have got Carry value, then create a na new node
			//associate it with link list and return
			if(carry > 0)
			{
				var carryNode = new LinkedListNode<int>(carry);
				var newList = new LinkedList<int>();
				newList.AddFirst(carryNode);
				return newList;
			}
			else 
				//return null otherwise
				return null;
		}
		
		//Add nodes and carry too
		var tempResult = firstNumNode.Value + secondNumNode.Value + carry;
		//Create a Empty List
		var resultList = new LinkedList<int>();
		//Create a new node using the above result assign it to the List.
		var newNode = new LinkedListNode<int>(tempResult % 10);
		resultList.AddFirst(newNode);
	
		//Go ove for other nodes
		var list = AddNumbers(firstNumNode.Next,secondNumNode.Next,tempResult/10);
		if(null != list && null != list.First)
		{
			while(null != list.First)
			{
				var node = list.First;
				//First remove the node from earlier list and then add it to result
				list.Remove(list.First);
				resultList.AddAfter(newNode,node);
				//cache it so that next node can be added after "node"
				newNode = node;
			}
		}	
		return resultList;
	}

Appreciate your feedback.

- .NetGeek June 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *link;
 
};
struct node *temp,*head=NULL;
int create(int val)
{
    struct node *newnode;
 
    newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = val;
    newnode->link= NULL;
 
    if(head==NULL)
    {
        head = newnode;
 
    }
    else
    {
        temp=head;
    while(temp->link!=NULL)
    {
        temp=temp->link;
 
    }
    temp->link= newnode;
    }
    return 0;
 
}
int display(struct node *head)
{
    temp=head;
    while(temp!=NULL)
    {
        printf("%d",temp->data);
        temp=temp->link;
        if(temp!=NULL)
        printf("->");
    }
    printf("\n");
    return 0;
}
 
struct node* reverse(struct node *head)
{
    struct node* prev   = NULL;
    struct node* current;
    struct node* next;
    current=head;
    while (current != NULL)
    {
        next  = current->link;  
        current->link = prev;   
        prev = current;
        current = next;
    }
    head = prev;
    return head;
}
struct node* addlist(struct node *head1,struct node *head2)
{
	int c =0,sum=0;
	struct node *temp1=head1;
	struct node *temp2=head2;
	struct node *head3=NULL;
	while(temp1!=NULL&&temp2!=NULL)
 
	{
 
		sum= temp1->data+temp2->data+c;
		c = sum/10;
		sum=sum%10;
 
 
	struct node* newnode = (struct node*)malloc(sizeof(struct node));
		newnode->data =sum;
		newnode->link=NULL;
		if(head3==NULL)
		head3=newnode;
		else
		{
			newnode->data =sum;
			newnode->link=head3;
			head3=newnode;
		}
 
		temp1=temp1->link;
		temp2= temp2->link;
 
	}
while(temp1==NULL&&temp2!=NULL)
{
	sum= temp2->data+c;
		c = sum/10;
		sum=sum%10;
		struct node* newnode = (struct node*)malloc(sizeof(struct node));
			newnode->data =sum;
			newnode->link=head3;
			head3=newnode;
				temp2= temp2->link;
}
while(temp1!=NULL&&temp2==NULL)
{
	sum= temp1->data+c;
		c = sum/10;
		sum=sum%10;
		struct node* newnode = (struct node*)malloc(sizeof(struct node));
			newnode->data =sum;
			newnode->link=head3;
			head3=newnode;
				temp1= temp1->link;
}
		if((temp1==NULL||temp2==NULL)&&c>0)
		{
			struct node* newnode = (struct node*)malloc(sizeof(struct node));
		newnode->data =c;
		newnode->link=head3;
			head3=newnode;
		}
	return head3;
}
int main()
{
      int n1,n2,v,i;
      printf("enter no ofnodes in 1st list\n");
      scanf("%d",&n1);
      for(i=0;i<n1;i++)
      {
          printf("enter val\n");
          scanf("%d",&v);
          create(v);
      }
      struct node *head1,*head3;
      head1=head;
 
      head=NULL;
 
     printf("enter no ofnodes in 2nd list\n");
      scanf("%d",&n2);
      for(i=0;i<n2;i++)
      {
          printf("enter val\n");
          scanf("%d",&v);
          create(v);
      }
       struct node *head2;
      head2=head;
        printf("first linkedlist\n");
    display(head1);
    head1 = reverse(head1);
 
      printf("second linkedlist\n");
   display(head2);
     head2 = reverse(head2);
     head3= addlist(head1,head2);
  display(head3);
 
    //code
    return 0;

}

- Anonymous September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This comment has been deleted.

- Administrator November 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The idea is reverse the two link lists. Add node by node and create another link list for each node by node additions. Adjust for any carry over. Now reverse the resultant link list to get the desired link list.

I'll post the code soon.

- Jit November 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

// Find the difference between the given linked list
// assuming its d(suppose 1st linked list is larger)
Node * temp1 = first1;// For first Linked List
Node *temp2 = first 2 ;//For second Linked List
for (int i = 0; i< d; i++)
temp1 = temp->next;
// Now start adding data and keep it in single Node from the left to right side
while( Temp1 != null)
{temp1->data += temp2->data;
temp1= temp1->next;
temp2 = temp2 -> next;
}
//Now start from first node of first list and check if any node data is greater than 10 then just add 1 to the left node of this node and subtract 10 from that.Repeat till all the data of linked list is less than 10
//boundary condition if first data i s greater than 10 we need to create a separate node and link it to first and make this node as first

while (true)
{
int flag = false;
if (first->data > 10)
{
// create new node
Node newnode = malloc (sizeof(node))
newnode->data = 1;
first->data -= 10;
newnode->next = first;
first = newnode;

flag = true;
}


temp1= first;
temp2 = first->next;
while(temp2 != null)
{
if(temp2->data >= 10)
{
temp2->data = temp2->data-10;
temp->data = temp1->data+1;
temp1= temp1->next;
temp2=temp2->next;
flag = true;
}
if(flag == false)
break;
}




}




{


}

- Adarsh Ranjan December 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

two loops.. ooh gush this is really over-engineered solution:
this can be done in a single loop: just go through the lists keeping a carry flag

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How do you plan to get the carry from the least significant digit to the most significant digit in a single loop?

example: 112+888

Other than the least significant digit, none of the digits themselves generate a carry. They only generate a carry once the least significant digit is calculated and the carry moves towards the left. That's why I used recursion above. But I agree with you about nested loops. They are unnecessary, the complexity shouldn't be greater than O(n).

- crdmp December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aah got you.. I overlooked that the numbers are originally stored in a twisted way, from most to least significant digit, while naturally it should be the other way around

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

so can anyone give a final solution using a single loop with time complexity O(n)

- coding for fun December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think just keep carry flag is not enough. If there are several consecutive 9s just before the current digit, then one carry should lead to change all the digits which containing 9 and one more before the consecutive 9s. Using a queue will be a good solution for me...I dont know why ppl dont like this method...

- yangqch December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am not sure what you're taking about..
if the nos are stored in a normal way, i.e., from least to most significant digit, then the addition can be done using the following loop:

int c = 0;
for(i = 0; i < n; i++) {
z[i] = x[i] + y[i] + c;
c = (z[i] >= 10);
if(c == 1)
  z[i] -= 10;
}

- Anonymous December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

keep the track of previous node of temp1.. if sum is greater than 10 then add the carry to previous node data and move previous node by next
.
while( Temp1 != null)
{temp1->data += temp2->data;
if (temp1->data > 10)
{
temp1->data = temp1->data %10;
prev->data = prev->data+1;
}
temp1= temp1->next;
temp2 = temp2 -> next;
prev= prev->next;

- Anonymous February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

keep the track of previous node of temp1.. if sum is greater than 10 then add the carry to previous node data and move previous node by next
.
while( Temp1 != null)
{temp1->data += temp2->data;
if (temp1->data > 10)
{
temp1->data = temp1->data %10;
prev->data = prev->data+1;
}
temp1= temp1->next;
temp2 = temp2 -> next;
prev= prev->next;

- Anonymous February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How about starting at the head of the list and pushing the numbers in a stack as we read them.
When end of list reached, pop out numbers from the stack and multiple them with increasing powers of 10 and keep adding them to the result.

- someone December 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the problem is 1. the number may be too big so that we prefer list to store it. 2. solve it in one pass.(adding to stack is like reversing the list)

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Set old number as 0, new data from link list
Now multiply old number with 10 and add link list number.
while(linklist->next != null)
Sum = old number* 10 + link list number
old number = sum
}

Answer is Sum

traver

- Anonymous December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oops got lot of typo mistakes

int sum = 0;
while(node != null)
{
sum = sum*10 + node->value;
node = node->next;
}

I hope it is more clear now

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

if the question means it should be finished in one pass(no turning back), I think the point is how to take care of '9', if it's 1999, you should keep all the four digits and when the summation of next digit is 10, your current result should be be 20000.

In my opinion, after determine which list is longer and their length difference, we can keep add corresponding digits one by one from the front to rear. In the procedure, we can use a Queue to store the node pointer of all the previous nodes we need to keep tracking. If the current digit is not 9, we can give up all the previous tracked nodes in the Queue.
The rule:
If current->value==9: Queue.enqueue(9)
if current->value>9: while(!Queue.isEmpty): Queue.dequeue()->value+1 //add more necessary code to take care of carry
Queue.enqueue(current->value%10)
if current->value<9: while(!Queue.isEmpty): Queue.dequeue()
Queue.enqueue(current->value)

- Anonymous December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

List add (List l1,List l2){
List l3 =new List();
if(l1 == Null && l2 == Null){
l3=null;
}
while(l1.next != Null && l2.next!= null){
l3.data = l1.data+ l2.data;
l3= l3.next;
}
if(l1.next){
l3.data = l1.data;
l3.next = l1.next;
}
else{
l3.data = l2.data;
l3.next = l2.next;
}

return l3;

}

- sweet.prash December 27, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More