i got this as an interview question. i was given 2 linked lists of unequal lengths,containing a single digited number in each of their nodes. i was asked to build a 3rd linked list which contains the sum of the two linked lists, again in the form of 1 digit in a node. ex: linked list 1 is 4-7-9-6 linked list 2 is 5-7 then the 3rd linked list would be 4-8-5-3 can someone suggest me an efficient algorithm, with minimum compromise in terms of space complexity?(i am not expecting an algo dat involves reversing the lists many times).
Asked
Active
Viewed 8,892 times
2
-
1In what way is the sum of 4-7-9-6 and 5-7 equal to 4-8-5-3? – manneorama Sep 24 '10 at 10:48
-
I have no idea. I was initially considering that it may be a case of aligning the ends of the lists and take sums mod 10, but then the result would've been 4-7-4-3. – Vatine Sep 24 '10 at 10:56
-
4I guess they're just integers, represented as lists of digits, so it's 4796 + 57 = 4853 ? – Paul R Sep 24 '10 at 10:56
-
ya, paul. thats exactly what i meant. sorry about not being clear with that. – wordwiz Sep 24 '10 at 11:05
-
I hazard to guess that the correct answer to the interview question is "Is the list single or double linked?" – Christoffer Sep 24 '10 at 11:28
-
Since the OP mentions reversing the lists, I assume singly linked. – AlcubierreDrive Sep 24 '10 at 11:31
-
it would be very easy if it were a doubly linked list. its a singly linked list. – wordwiz Sep 24 '10 at 11:32
-
Maybe it was a good idea to ask "Why not keep them reversed all the time?" – ruslik Sep 24 '10 at 23:42
6 Answers
3
- Reverse lists 1 and 2
- Sum element-by-element (while maintaining a carry), putting the results in a list 3 that you construct from tail to head
OR
- Convert lists 1 and 2 to ints (e.g.
int list1AsInt = 0; For each node {list1AsInt *= 10; list1AsInt += valueOfThisNode;}
) - Sum those ints
- Convert the result to a linked list (e.g.
valueOfBrandNewNode = list3AsInt % 10; list3AsInt /= 10; Add a new node that points to the prev one;
)
OR
- Traverse both lists once to find out their lengths. For this example, let's assume that list 1 is longer by N nodes.
- Create a list 3 to represent the sum without carries and a list 4 to represent the carries.
- For the first N nodes of list 1, copy those values to list 3 and make list 4's values be 0.
- For the remaining nodes of lists 1 and 2, sum element-by-element, putting the sum mod 10 in list 3 and the carry in list 4. Keep track via a bool of whether list 4 is all 0's.
- Add a last node with value 0 to list 4.
- If list 4 is entirely 0's, done. Else, recurse to step 2, treating list 3 as the new list 1 and list 4 as the new list 2. We know the length of the new list 1 is the larger of the lengths of the old lists 1 and 2, and the length of the new list 2 is one more than that.

AlcubierreDrive
- 3,654
- 2
- 29
- 45
-
the 2nd soln wudnt work when the length of the lists is so long that the resulting integer cant be stored as an int. – wordwiz Sep 24 '10 at 11:30
-
and is there any other alternative to the 1st soln, where i dont have to reverse the lists? – wordwiz Sep 24 '10 at 11:31
-
I added a 3rd alternative that does not require reversing the lists, but its speed is very dependent on how many carries will be necessary. Each carry can require up to 1 additional traversal of both lists. – AlcubierreDrive Sep 24 '10 at 11:42
-
2+1 for good alternatives. Re #1, worth noting that list reversal is possible in place. Also, hybrids are possible: #2 as traversing but counting nodes, so on overflow can revert to #3. Can also simply read nodes into std::vector
then sum from the vectors. Optimising #3: fixed-length window to speed carries, or save one/many/all node* N elements apart from before current node-summing point, to reduce rescans from head. Or add ignoring carry (9+5=14) then move 2(+) pointers to consecutive nodes through a normalisation loop, carrying back a node at a time, until a loop finds no work. – Tony Delroy Sep 28 '10 at 02:21
0
Take a look at this code:
node *add_two_linkedlist(node *head1,node *head2)
{
int i,j,temp;
node *p,*n;
p=head1;
n=head2;
i=count(head1);
j=count(head2);
if(i>j)
{
while(j!=0)
{
p->data=p->data+n->data;
if(p->data>10)
{
temp=(p->data)/10;
p->data=(p->data)%10;
p=p->next;
n=n->next;
p=p->data+temp;
j--;
}
}
return head1;
}
if(j>i)
{
while(i!=0)
{
n->data=p->data+n->data;
if(n->data>10)
{
temp=(n->data)/10;
n->data=(n->data)%10;
n=n->next;
p=p->next;
n=n->data+temp;
i--;
}
}
return head2;
}
}
0
This is straightforward. Assuming the leftmost node is the most significant bit. Align the two lists, add and propagate carry. Upon return create a new node if required..
#include <stdio.h>
struct list {
int val;
struct list * next;
};
int listadd (struct list *l1, struct list *l2) {
if ((l1 == NULL) || (l2 == NULL))
return;
int carry = 0;
if ((l1->next == NULL) && (l2->next != NULL)) {
carry += listadd (l1, l2->next) + l2->val;
return carry;
}
else if ((l1->next != NULL) && (l2->next == NULL)) {
carry +=listadd (l1->next, l2);
l1->val = l1->val + carry;
}
else if ((l1->next != NULL) && (l2->next != NULL)) {
carry += listadd (l1->next, l2->next);
}
else if ((l1->next == NULL) && (l2->next == NULL)) {
l1->val = l1->val + l2->val;
carry = l1->val/10;
l1->val = l1->val%10;
return carry;
}
carry = l1->val/10;
l1->val = l1->val%10;
return carry;
}
struct list * createnode (int val) {
struct list * temp = (struct list *) malloc (sizeof(struct list));
temp->val = val;
temp->next = NULL;
return temp;
}
int main() {
int carry = 0;
struct list *l1 = createnode(1);
l1->next = createnode(2);
struct list *l2 = createnode(7);
l2->next = createnode(8);
carry = listadd(l1,l2);
if (carry != 0) {
struct list * temp = createnode(carry);
temp->next = l1;
l1 = temp;
}
while (l1!= NULL) {
printf ("%d", l1->val);
l1=l1->next;
}
}

asim kadav
- 23
- 2
0
- Read each digit as its ASCII equivalent into a char array indexed from 0, for both lists.
- Use the
atoi()
function on both char arrays ( you may useatol()
oratoll()
if you are concerned about the length) - Add both numbers
- Use the
itoa()
function to convert to a char array & then put back into new list.
Although, I admit the itoa()
function is not standard.
-
This would work only so long as your linked lists represented numbers that fit within the machine word. There's no reason there couldn't be a billion elements in a linked list. – Gabe Sep 27 '10 at 03:58
0
If the lists are doubly linked it's easy:
- Traverse both lists to the end.
- Add the digits in corresponding nodes, and keep the carry digit.
- Create the node in list 3.
- Move one node towards the start of the lists and repeat.

Andrew Cooper
- 32,176
- 5
- 81
- 116
0
The solution could be much simpler if the list stored the numbers in reverse order.
Nevertheless, with the given constraint, here is an approach.
- find the nthToLast digit of both lists, starting with
n = 0
, - create a
node
with the sum of the digits, - update the (running)
carry
, insert
the newly created node at thehead of
theresult
list
Following is the (untested) C code.
typedef struct DigitNode_ {
int digit;
struct DigitNode_ * next;
} DigitNode;
/* Returns the n-th element from the end of the SLL;
if no such element exists, then return NULL.
See: https://stackoverflow.com/questions/2598348/
*/
extern DigitNode * nthNodeFromTail( DigitNode * listHead, size_t n );
/* Push pNode in the front, i.e. as the new head of the list */
extern void pushFront( DigitNode ** pListHead, DigitNode * pNode );
/* Create new list as sum of a and b, and return the head of the new list.
a -> 4 -> 7 -> 9 -> 6 -> NULL
b -> 5 -> 7 -> NULL
results in
c -> 4 -> 8 -> 5 -> 3 -> NULL
*/
DigitNode * sumDigitLists( DigitNode * a, DigitNode * b ) {
DigitNode * c = 0;
int carry = 0;
/* i is the position of a node from the tail of the list, backwards */
for( size_t i = 0; /* see 'break' inside */; i++ ) {
const DigitNode * const ithNodeA = nthNodeFromTail( a, i );
const DigitNode * const ithNodeB = nthNodeFromTail( b, i );
/* Stop when processing of both lists are finished */
if( !ithNodeA && !ithNodeB ) {
break;
}
const int ithDigitA = ithNodeA ? ithNodeA->digit : 0;
const int ithDigitB = ithNodeB ? ithNodeB->digit : 0;
assert( (0 <= ithDigitA) && (ithDigitA <= 9) );
assert( (0 <= ithDigitB) && (ithDigitB <= 9) );
const int conceptualIthDigitC = carry + ithDigitA + ithDigitB;
const int ithDigitC = conceptualIthDigitC % 10;
carry = conceptualIthDigitC / 10;
DigitNode ithNodeC = { ithDigitC, NULL };
pushFront( &c, &ithNodeC );
}
return c;
}