leetcode-solution/Python/0445-add-two-numbers-ii.py at main · hogan-tech/leetcode-solution · 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
41
# time complexity: O(m+n)
# space complexity: O(m+n)
from typing import Optional


class Solution:
    def reverseList(self, node: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while node:
            nextNode = node.next
            node.next = prev
            prev = node
            node = nextNode
        return prev

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        r1 = self.reverseList(l1)
        r2 = self.reverseList(l2)

        totalSum = 0
        carry = 0
        result = ListNode()
        while r1 or r2:
            if r1:
                totalSum += r1.val
                r1 = r1.next
            if r2:
                totalSum += r2.val
                r2 = r2.next

            result.val = totalSum % 10
            carry = totalSum // 10
            head = ListNode(carry)
            head.next = result
            result = head
            totalSum = carry

        return result.next if carry == 0 else result