LeetCode: Add Two Numbers

Add two numbers represented by linked lists.

I love this problem! It is the standard addition algorithm represented using linked lists. Let’s consider the following example: 342 + 465.

Turn this into two linked lists:

l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4

Solution

We need to track a carry digit. This defaults to 0.

• Add the values of the two nodes and the carry digit: 0 + 2 + 5 = 7
• Integer divide by 10 to get the next carry: 7 // 10 = 0
• Subtract 10 * the carry digit to get the value. 7 - 10 * 0 = 7
• Create a new node with value 7.
• Move to the next digit.
• Repeat until both linked lists are exhausted.
• If there is a remaining carry digit, create a new node with that value.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        answer = ln = ListNode(0)
        carry = 0

        while l1 or l2:
            value = carry
            value += l1.val if l1 else 0
            value += l2.val if l2 else 0

            carry = value // 10
            value -= 10 * carry

            ln.next = ListNode(value)
            ln = ln.next

            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        if carry > 0:
            ln.next = ListNode(carry)

        return answer.next