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.

題目連結

思路

兩個 linked list 要處理相加的問題，有點類似一個位數一個位數拆開來獨立相加，由前往後分別代表位數從 0, 1, 2 一路往上增加，但由於兩個 linked list 長度不一 (兩個數字位數不同)，因此使用迴圈一位一位相加處理在判斷上會需要考慮比較多狀況，例如一邊已經走完到 null 但是另一邊還沒，或是兩邊都走到 null 但還有進位要處理等等。

因此最後的做法是直接先將兩個 linked list 轉換回一般數字，直接相加之後再把結果轉換回 linked list 的形式，在邏輯上會比較直觀一些。首先定義處理 linked list -> integer 的函式：

def calculateNumber(l: Optional[ListNode]) -> int:
    num = 0
    digit = 0

    while l is not None:
        num += l.val * 10**digit
        digit += 1
        l = l.next
        
    return num

將兩個 linked list 轉回數字相加後再變回 linked list：

def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    num_l1 = calculateNumber(l1)
    num_l2 = calculateNumber(l2)
    totalStr = [i for i in str(num_l1 + num_l2)]

    ans = ListNode()
    current = ans
    # 因為 linked list 是從個位數開始往後所以要將陣列倒序讀取
    for idx, digit in enumerate(totalStr[::-1]):
        current.val = int(digit)
        if idx + 1 != len(totalStr):           
            current.next = ListNode()
            current = current.next

    return ans

Full Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def calculateNumber(self, l: Optional[ListNode]):
        num = 0
        digit = 0

        while l is not None:
            num += l.val * 10**digit
            digit += 1
            l = l.next
        
        return num

    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        num_l1 = self.calculateNumber(l1)
        num_l2 = self.calculateNumber(l2)
        totalStr = [i for i in str(num_l1 + num_l2)]

        ans = ListNode()
        current = ans
        for idx, digit in enumerate(totalStr[::-1]):
            current.val = int(digit)
            if idx + 1 == len(totalStr):
                break
            current.next = ListNode()
            current = current.next

        return ans