add_two_numbers

View Source

 1from utils import ListNode
 2from typing import Optional
 3
 4
 5# @leet start
 6class Solution:
 7    def addTwoNumbers(
 8        self, l1: Optional[ListNode], l2: Optional[ListNode]
 9    ) -> Optional[ListNode]:
10        """
11        To add two linked list, we can employ the grade school addition algorithm.
12
13        While both lists have a member, we can use divmod 10 to get the carry
14        and the digit to place in the resulting linked list node.
15
16        Finally, we have to increment the two list nodes and the result.
17
18        At the end we may have one list with remaining members, so we do the same
19        algorithm, just without the other list.
20
21        Finally, we have to make sure to save the carry if it still exists after
22        all this time into the last linked list node.
23        """
24        carry = 0
25        dummy = ListNode()
26        ret_node = dummy
27
28        def add_to_end(l):
29            nonlocal carry, dummy
30            while l:
31                carry, digit = divmod(l.val + carry, 10)
32                new_node = ListNode(digit)
33                dummy.next = new_node
34                dummy = dummy.next
35                l = l.next
36
37        while l1 and l2:
38            carry, digit = divmod(l1.val + l2.val + carry, 10)
39            new_node = ListNode(digit)
40            dummy.next = new_node
41            dummy = dummy.next
42            l1 = l1.next
43            l2 = l2.next
44
45        add_to_end(l1)
46        add_to_end(l2)
47        if carry:
48            dummy.next = ListNode(carry)
49
50        return ret_node.next
51
52
53# @leet end
54
55
56def test():
57    assert 2 + 2 == 4

class Solution: View Source

 7class Solution:
 8    def addTwoNumbers(
 9        self, l1: Optional[ListNode], l2: Optional[ListNode]
10    ) -> Optional[ListNode]:
11        """
12        To add two linked list, we can employ the grade school addition algorithm.
13
14        While both lists have a member, we can use divmod 10 to get the carry
15        and the digit to place in the resulting linked list node.
16
17        Finally, we have to increment the two list nodes and the result.
18
19        At the end we may have one list with remaining members, so we do the same
20        algorithm, just without the other list.
21
22        Finally, we have to make sure to save the carry if it still exists after
23        all this time into the last linked list node.
24        """
25        carry = 0
26        dummy = ListNode()
27        ret_node = dummy
28
29        def add_to_end(l):
30            nonlocal carry, dummy
31            while l:
32                carry, digit = divmod(l.val + carry, 10)
33                new_node = ListNode(digit)
34                dummy.next = new_node
35                dummy = dummy.next
36                l = l.next
37
38        while l1 and l2:
39            carry, digit = divmod(l1.val + l2.val + carry, 10)
40            new_node = ListNode(digit)
41            dummy.next = new_node
42            dummy = dummy.next
43            l1 = l1.next
44            l2 = l2.next
45
46        add_to_end(l1)
47        add_to_end(l2)
48        if carry:
49            dummy.next = ListNode(carry)
50
51        return ret_node.next

def addTwoNumbers( self, l1: Optional[utils.ListNode], l2: Optional[utils.ListNode]) -> Optional[utils.ListNode]: View Source

 8    def addTwoNumbers(
 9        self, l1: Optional[ListNode], l2: Optional[ListNode]
10    ) -> Optional[ListNode]:
11        """
12        To add two linked list, we can employ the grade school addition algorithm.
13
14        While both lists have a member, we can use divmod 10 to get the carry
15        and the digit to place in the resulting linked list node.
16
17        Finally, we have to increment the two list nodes and the result.
18
19        At the end we may have one list with remaining members, so we do the same
20        algorithm, just without the other list.
21
22        Finally, we have to make sure to save the carry if it still exists after
23        all this time into the last linked list node.
24        """
25        carry = 0
26        dummy = ListNode()
27        ret_node = dummy
28
29        def add_to_end(l):
30            nonlocal carry, dummy
31            while l:
32                carry, digit = divmod(l.val + carry, 10)
33                new_node = ListNode(digit)
34                dummy.next = new_node
35                dummy = dummy.next
36                l = l.next
37
38        while l1 and l2:
39            carry, digit = divmod(l1.val + l2.val + carry, 10)
40            new_node = ListNode(digit)
41            dummy.next = new_node
42            dummy = dummy.next
43            l1 = l1.next
44            l2 = l2.next
45
46        add_to_end(l1)
47        add_to_end(l2)
48        if carry:
49            dummy.next = ListNode(carry)
50
51        return ret_node.next

To add two linked list, we can employ the grade school addition algorithm.

While both lists have a member, we can use divmod 10 to get the carry and the digit to place in the resulting linked list node.

Finally, we have to increment the two list nodes and the result.

At the end we may have one list with remaining members, so we do the same algorithm, just without the other list.

Finally, we have to make sure to save the carry if it still exists after all this time into the last linked list node.

def test(): View Source

57def test():
58    assert 2 + 2 == 4