LeetCode 2. Add Two Numbers

題目

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

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

給定兩個代表兩個非負整數的非空鏈結串列。這些數字以相反的順序存儲，並且它們的每個節點都包含一個數字。將兩個數字相加並且返回作為鏈結串列的總和。

您可以假設這兩個數字不包含任何前導0，除了數字0本身除外。

注: 前導0就是有像是情報員編號0028526，這種0開頭的數字

範例1:

輸入: l1 = [2,4,3], l2 = [5,6,4]
輸出: [7,0,8]
解釋: 342 + 465 = 807.

範例2:

輸入: l1 = [0], l2 = [0]
輸出: [0]

範例3:

輸入: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出: [8,9,9,9,0,0,0,1]

限制:

• 每個鏈結串列中的節點數在 [1, 100] 範圍內。
• 0 <= Node.val <= 9
• 保證該串列表示一個沒有前導零的數字。

以下以範例一為例，需注意數字以相反的順序存儲

果斷放棄的解決方法

2 + 4 * 10 + 3 * 100 = 342
這種乘10的方法會造成溢位

解決辦法

使用國小基礎的直式加法運算來解這題

 342
+465
-----
 807

第1步
l1[0] + l2[0] = 2 + 5 = 7

第2步
l1[1] + l2[1] = 4 + 6 = 10
寫0，然後進1位

第3步
l1[2] + l2[2] = 3 + 4 = 7
剛進1位
7 + 1 = 8

將這些步驟程式化，在程式中會有一些檢查工作
例如 4 + 6 = 10 我要寫0，並記錄要進1位

解答

python

class ListNode:
    # Definition for singly-linked list.
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(
        self,
        l1: Optional[ListNode],
        l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        # 是否進位
        carry = False
        # 當前 ListNode
        current_list_node = None
        # 上個 ListNode
        last_list_node = None
        result = None

        while(l1 is not None or l2 is not None or carry is True):
            value1 = 0
            value2 = 0

            if(l1 is not None):
                value1 = l1.val
                l1 = l1.next

            if(l2 is not None):
                value2 = l2.val
                l2 = l2.next

            # 此次節點得值
            current_value = value1 + value2

            if carry:
                current_value += 1
                carry = False

            if current_value >= 10:
                current_value %= 10
                carry = True

            current_list_node = ListNode(current_value)

            if result is None:
                result = current_list_node

            if last_list_node is not None:
                last_list_node.next = current_list_node

            last_list_node = current_list_node

        return result