adding two linked lists efficiently in C

Question

I have two linked lists representing the digits of decimal numbers in order from most- to least-significant. for eg 4->7->9->6 and 5->7 The answer should be 4->8->5->3 without reversing the lists because reversing the lists would result in decrease of efficiency.

I am thinking of solving the problem using stack.I will traverse both the lists and push the data elements into two separate stacks.One for each linked list.Then I pop both the stacks together and add both the elements and if the result is a two digit no I 10 modulo it and store the carry in a temp variable.The remainder is stored in the node and the carry is added to the next sum and so on. if the two stacks are s1 and s2 and the result linked list is res.

temp = 0;
res = (node*)(malloc(sizeof(node*));

while(s1->top!=-1 || s2->top!=-1)
{  
    temp = 0;
    sum = pop(s1) + pop(s2);
    n1 = (node*)(malloc(sizeof(node*));
    temp = sum/10;
    sum = sum%10;
    sum = sum+temp;
    n1->data = sum;
    n1->next = res;
    res = n1;
    free n1;
    //temp=0;
}

if((s1->top==-1)&&(s2->top==-1))
{
    return res;
}
else if(s1->top==-1)
{
    while(s2->top!=-1)
    {
        temp = 0;
        sum = pop(s2);
        sum = sum + temp;
        temp = sum/10;
        sum = sum%10;
        n1 = (node*)(malloc(sizeof(node*));
        n1->data = sum;
        n1->next = res;
        res = n1;
        free n1;
    }
}
else
{
    while(s2->top!=-1)
    {
        temp = 0;
        sum = pop(s2);
        sum = sum+temp;
        temp = sum/10;
        sum = sum%10;
        n1=(node*)(malloc(sizeof(node*));
        n1->data = sum;
        n1->next = res;
        res = n1;
        free n1;
    }
}

return res; 

I have come across this problem many times in interview questions but this is the best solution that I could think of. If anyone can come with something more efficient in c i will be very glad.

Answer 1

Two passes, no stack:

• Get the length of the two lists.

• Create a solution list with one node. Initialize the value of this node to zero. This will hold the carry digit. Set a list pointer (call it the carry pointer) to the location of this node. Set a list pointer (call it the end pointer) to the location of this node.

• Starting with the longer list, for each excess node, link a new node to the end pointer and assign it the value of the excess node. Set the end pointer to this new node. If the value is less than 9, set the carry pointer to the new node.

• Now we're left with both list pointers having the same number of nodes in each.

• While the lists are not empty...

  • Link a new node to the end pointer and advance the end pointer to this node.

  • Get the values from each list and advance each list pointer to the next node.

  • Add the two values together.

    1. If value is greater than nine, set the value to value mod 10, increment the value held in the carry pointer's node, move the carry pointer to the next node. If carry pointer's value is nine, set to zero and go to next node.

    2. If value is nine. Set it. Do nothing else.

    3. If value is less than nine. Set it. Set carry pointer to current node.

• When you're done with both lists, check if the solution pointer's node value is zero. If it is, set the solution pointer to the next node, deleting the unneeded extra digit.

Answer 2

This is how I would go about solving this:

Step 1: Make a pass on both linked lists, find lengths

say len(L1) = m and len(L2) = n

Step 2: Find difference of lengths

if ( m > n )
    d = m - n
else if ( n > m )
    d = n - m
else
    d = 0

Step 3: Move a temporary pointer d ahead of the larger list

Step 4: Now we have two linked lists to add whose lengths are same, so add them recursively, maintaining a carry.

Step 5: ( Note: if ( d == 0 ) don't perform this step )

After step 4, we've got partial output list, and now we have to put remaining of the larger list at the beginning of output list.

if ( d > 0 )
    -Travel larger list till d positions recursively
    -Append sum = value_at_end + carry (update carry if sum >= 10) to output list at beginning
    -Repeat until difference is consumed

Note: I'm solving the problem as its put before me, not by suggesting the change in underlying data structure.

Time complexity:

1. Making single passes on both the lists to find their lengths: O(m+n)
2. Summing two linked lists of equal size (m - d and n) recursively: O(n), assuming m > n
3. Appending remaining of larger list to output list: O(d)

Total: O( (m+n) + (n) + (d) ) OR O(m+n)

Space complexity:

1. step 2 of time complexity: O(n), run time stack space
2. step 3 of time complexity: O(d), run time stack space

Total: O(n + d) OR O(n)

Answer 3

I'd just find the total value of each linked list separately, add them together, then transform that number into a new linked list. So convert 4->7->9->6 and 5->7 to integers with the values 4796 and 57, respectively. Add those together to get 4853, then transform that into a linked list containing 4->8->5->3. You can do the transformations with simple math.

Doing it your way would be a lot easier if you changed the way that the numbers are represented in the first place. Make it so the ones digit is always first, followed by the tens digit, followed by hundreds, etc.

EDIT: Since you're apparently using enormous numbers: have you considered making them doubly-linked lists? Then you wouldn't need to reverse it, per se. Just traverse it backwards.

Answer 4

Using a stack is no more efficient than reversing the lists (actually it is reversing the lists). If your stack object is dynamically allocated this is no big deal, but if you create it with call recursion, you'll easily get Stack Overflow of the bad sort. :-)

Answer 5

If you doubly link the lists, you can add the digits and use the backwards links to find out where to put your carried value. http://en.wikipedia.org/wiki/Doubly_linked_list