Adding two linked lists efficiently in C

Question

I have two linked lists representing decimal digits in order from most to least significant. for example, 4->7->9->6 and 5->7 answer should be 4->8->5->3 without changing the lists, since changing the lists will lead to a decrease in efficiency.

I am thinking of solving a problem using stack.I will go through both lists and push data items into two separate stacks.One for each linked list. Then I will pop both stacks together and add both elements, and if the result is a two-digit number I'm 10 modulo and save the transfer in the temp variable. The rest is stored in node, and the carry is added to the next sum, etc. if two stacks are s1 and s2, and the list associated with the result 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 often came across this problem in interview matters, but this is the best solution I could think of. If someone can come up with something more efficient in c, I will be very happy.

Answer 1

Two passes, no stack:

• Get the length of two lists.

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

• Starting with a longer list, for each excess node, associate a new node with a trailing 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 have both list pointers with the same number of nodes in each.

• Until the lists are empty ...

  • Link the new node to the end pointer and move the end pointer to that node.

  • Get the values ​​from each list and move the pointer of each list to the next node.

  • Add two values ​​together.

    • If the value is more than nine, set the value to value mod 10 , increase the value held by the transfer pointer node, move the transfer pointer to the next node. If the carry pointer is nine, set the value to 0 and go to the next node.

    • If the value is nine. Install it. Do nothing else.

    • If the value is less than nine. Install it. Set the carry pointer to the current node.

• When you are done with both lists, check if the value of the solution pointer is node. If so, set the solution pointer to the next node, removing the unnecessary extra digit.

Answer 2

Here's how I decided to solve it:

Step 1: Pass through both linked lists, find the lengths

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

Step 2: Find the difference in lengths

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

Step 3: Move the temporary pointer d in front of the large list

Step 4: Now we have two linked lists for adding, the length of which is the same, so add them recursively, supporting hyphenation.

Step 5: ( Note: if (d == 0) does not complete this step)

After step 4, we have a partial list of output, and now we need to put the remaining list from a larger list at the top of the list of results.

 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 solve the problem because it is put before me, and not by suggesting a change in the underlying data structure.

Time complexity:

• Creating single passes in both lists to find their length: O(m+n)
• Recursive summation of two linked lists of equal size (m - d and n): O(n) , assuming m > n
• Adding the remaining list of a larger list to the output list: O(d)

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

The complexity of the space:

• time step 2: O(n) , runtime stack space
• step 3 of time complexity: O(d) , runtime stack space

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

Answer 3

I would simply find the common value of each linked list separately, add them together, and then convert that number to a new linked list. Therefore, we convert 4-> 7-> 9-> 6 and 5-> 7 to integers with values ​​of 4796 and 57, respectively. Add them together to get 4853, and then convert them to a linked list containing 4-> 8-> 5-> 3. You can do the transforms using simple math.

Doing this would be a lot easier if you changed the way you represent numbers in the first place. Make sure that each digit is always the first, followed by dozens, and then hundreds, etc.

EDIT: Since you are apparently using huge numbers: do you think you make them double linked lists? Then you would not need to reverse it, as such. Just go back.

Answer 4

Using a stack is no more efficient than reversing lists (actually, reversing lists). If your stack object is dynamically allocated, that doesn't really matter, but if you create it with call recursion, you will easily get a poor sort stack overflow. :-)

Answer 5

If you double-link the lists, you can add numbers and use backlinks to find out where to put your carried value. http://en.wikipedia.org/wiki/Doubly_linked_list