Python: Add Two Numbers – Linked List

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contains a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:
789 + 478 = 1267

Input: (9 -> 8 -> 7) + (8 -> 7 -> 4)
Output: 7 -> 6 -> 2 -> 1

class Node:
    def __init__(self, x, nextNode = None):
        self.val = x
        self.next = nextNode
 
def printList(l):
    value = []
    while(l):
        value.append(l.val)
        l = l.next
    print(' -> '.join(map(str, value)))
 
def addTwoNumbers(l1, l2):
    """
    :type l1: Node
    :type l2: Node
    :rtype: Node
    """
    sum = l1.val + l2.val
    carry = int(sum / 10)
 
    l3 = Node(sum%10)
    p1 = l1.next
    p2 = l2.next
    p3 = l3
    while(p1 != None or p2 != None):
        sum = carry + ( p1.val if p1 else 0) + ( p2.val if p2 else 0)
        carry = int(sum/10)
        p3.next = Node(sum % 10)
        p3 = p3.next
        p1 = p1.next if p1 else None
        p2 = p2.next if p2 else None
 
    if(carry > 0):
        p3.next = Node(carry)
 
    return l3
 
#789
l1 = Node(9, Node(8, Node(7)))
printList(l1)
#478
l2 = Node(8, Node(7, Node(4)))
printList(l2)
l3 = addTwoNumbers(l1, l2)
printList(l3)   
print()   
#342
l1 = Node(2, Node(4, Node(3)))
printList(l1)
#465
l2 = Node(5, Node(6, Node(4)))
printList(l2)
l3 = addTwoNumbers(l1, l2)
printList(l3)

Output:

9 -> 8 -> 7
8 -> 7 -> 4
7 -> 6 -> 2 -> 1
 
2 -> 4 -> 3
5 -> 6 -> 4
7 -> 0 -> 8

Hope it helps.

Leave a comment

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.