Python: Add Two or More Numbers – Linked List

Dipin Krishna

6 years ago

You are given two or more 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 numbers and return them as a linked list.

You may assume the 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 addNumbers(*lists):
    """
    :type lists: List[Node]
    :rtype: Node
    """
    if not lists:
        return None
 
    l3 = Node(0)
    p3 = l3
    carry = 0
 
    while any(lists) or carry:
        total = carry
        for l in lists:
            if l:
                total += l.val
                l = l.next
 
        carry = total // 10
        p3.next = Node(total % 10)
        p3 = p3.next
 
        lists = [l.next if l else None for l in lists]
 
    return l3.next
 
#789
l1 = Node(9, Node(8, Node(7)))
printList(l1)
#478
l2 = Node(8, Node(7, Node(4)))
printList(l2)
l3 = addNumbers(l1, l2)
printList(l3)   
print()   
#342
l1 = Node(2, Node(4, Node(3, Node(5))))
printList(l1)
#26465
l2 = Node(5, Node(6, Node(4, Node(6, Node(2)))))
printList(l2)
#8712
l3 = Node(1, Node(2, Node(7, Node(8))))
printList(l3)
l4 = addNumbers(l1, l2, l3)
printList(l4)

Output:

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

Hope it helps.