CompetitiveProgrammingSolutions/Add Two Numbers II at main · Danitilahun/CompetitiveProgrammingSolutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def add(l1: Optional[ListNode], l2: Optional[ListNode]) -> tuple[int, Union[None, ListNode]]:
    if not l1 or not l2:
        #print(f"reached the end")
        return (0, None)
    addend_carry, result = add(l1.next, l2.next)
    sum_carry, val = divmod(l1.val + l2.val + addend_carry, 10)
    #print(f"{l1.val} + {l2.val} + {addend_carry} = {val} carry {sum_carry}")

    result = ListNode(val, result)
    return (sum_carry, result)

def length(ln: Optional[ListNode]) -> int:
    if not ln:
        return 0
    return length(ln.next) + 1

def left_pad(padding: int, ln: ListNode) -> ListNode:
    if padding <= 0:
        return ln
    return left_pad(padding - 1, ListNode(0, ln))

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        l1_size = length(l1)
        l2_size = length(l2)

        padded_l1 = left_pad(max(0, l2_size - l1_size), l1)
        padded_l2 = left_pad(max(0, l1_size - l2_size), l2)

        carry, result = add(padded_l1, padded_l2)
        if carry:
            result = ListNode(carry, result)
        return result