AN_SH 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
Correct Addition : 2600 2->6->0->0
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.
def addRecursively(self, h1, h2, carry):
if h1 == None and h2 == None:
return None
self.addRecursively( h1.next, h2.next, carry)

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) :
if self.head == None:
self.head = Node(data)
else:
node = Node(data)
node.next = self.head
self.head =node
return self.head
# ===== Addition function to add element using stack =====

def addRecursively(self, h1, h2):
if h1 == None and h2 == None:
return 0
# carry will be returned by recursive call
carry = self.addRecursively( h1.next, h2.next)

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

Answer Source

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
def addRecursively(self, h1, h2):
    if h1 == None and h2 == None:
        return 0

    # carry will be returned by recursive call
    carry = self.addRecursively( h1.next, h2.next)

    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