 AN_SH -4 years ago 70
Python Question

# Adding Two num­bers rep­re­sented by a linked list, Num­ber Stored in FORWARD order- Python

I am trying to add two numbers represented by Linked List in FORWARD direction. I have written the function to add them, but I am unable to understand how to forward carry to next level. It is turning out to be zero all time. Please advise me corrections in add function below,

Update1# I have written padding functionto make linked lists of equal length by adding zero to front of smaller number as below,

``````**Input:**
First Number     : 351            0->3->5->1
Second Number    : 2249           2->2->4->9
The result I am getting is 2590   2->5->9->0
``````

It is doing the addition correctly, but not able to forward carry to next level.

``````=======================  Code   ============================
#The carry is passed as zero.
if h1 == None and h2 == None:
return None

print "h1.val: ", h1.data," h2.val: ", h2.data, " Carry: ", carry
num =carry
if h1:
num +=h1.data
if h2:
num +=h2.data
carry = 1 if num>=10 else 0
num = num % 10
print "num: ", num, " carry: ",carry

=============================================================
Output:
h1.val:  1  h2.val:  9  Carry:  0
num:  0  carry:  1
h1.val:  5  h2.val:  4  Carry:  0
num:  9  carry:  0
h1.val:  3  h2.val:  2  Carry:  0
num:  5  carry:  0
h1.val:  0  h2.val:  2  Carry:  0
num:  2  carry:  0
``````

Update#2:

``````    def saveToLL(self, data) :
else:
node = Node(data)

if h1 == None and h2 == None:
return 0
# carry will be returned by recursive call

print "h1.val: ", h1.data," h2.val: ", h2.data, " Carry: ", carry
num = carry
if h1:
num +=h1.data
if h2:
num +=h2.data

# now return the carry of the current addition
carry_ret = 1 if num >= 10 else 0
# this should be set somewhere in self or one of the lists?
num = num % 10
self.saveToLL(num)
return carry_ret
`````` gowrath

The issue is that you need the recursive call to tell you whether there was a carry in the recursive addition that you need to add to the current position. For example, if you call add as `addRecursively(1->2, 1->9)`, it is going to recursively call `addRecursively(2, 9)` and the first call needs to know to add an extra 1 to the addition of 1 + 1 (the 0th position digits).

I don't know how your code is setting values in the class that is keeping track of the numbers, but what you can do is have the recursive call return how much to carry:

``````# No carry passed in
if h1 == None and h2 == None:
return 0

# carry will be returned by recursive call

num = carry

if h1:
num += h1.data
if h2:
num += h2.data

num = num % 10

self.saveToLL(num)

# now return the carry of the current addition
return 1 if num >= 10 else 0
``````

I take it the code you posted is more pseudocode and not the exact code you are using? It never seems to set anything of self or either of the lists. Am I missing something?

You can do what you are trying to do by passing carry into the recursive call and having it set the value of carry, but then you need to pass the carry "by reference" so that the changes persist. To do this, you could wrap the int in a class (say a Digit class?).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download