LeetCode 解題筆記：2. Add Two Numbers

作者：王一哲
日期：2026年7月8日


LeetCode 題目連結：2. Add Two Numbers

解題想法

中等難度題。題目給兩個鏈結串列，串列的節點數量為 1 到 100 個，每個節點各儲存一個 0 到 9 之間的整數，將串列中所有的節點數值接起來再反向，可以組成一個新的整數。題目要將兩個整數相加，再建一個新的鏈結串列，將相加後的值反向儲存到新串列的節點中。主要分為兩個步驟：

1. 遍歷鏈結串列 l1, l2，讀取串列中儲存的反序整數。
2. 計算加總，建一個新的鏈結串列儲存加總。

由於這題的節點數量很多，整數最多可達 100 位，如果用 C++ 解題需要處理大數加法，可以用字串或是陣列儲存超長整數。但是 Python 支援大數運算，可以先用字串儲存反序的整數，再用字串切片、int、str 的方式轉型，程式碼寫起來很簡短。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.18 MB, beats 95.92%.

# Definition for singly-linked list.
# class ListNode:
#     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]:
        # 遍歷鏈結串列 l1, l2，讀取串列中儲存的反序整數
        num1, num2 = "", ""
        while l1:
            num1 += str(l1.val)
            l1 = l1.next
        
        while l2:
            num2 += str(l2.val)
            l2 = l2.next
        
        # 計算加總，建一個新的鏈結串列儲存加總
        isum = str(int(num1[::-1]) + int(num2[::-1]))[::-1]
        head = ListNode(int(isum[0]))
        n = len(isum)
        dummy = head
        for i in range(1, n):
            dummy.next = ListNode(int(isum[i]))
            dummy = dummy.next
        
        return head

C++ 程式碼

Runtime: 1 ms, beats 45.38%. Memory: 77.05 MB, beats 75.05%.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    /* 自訂函式，用字串格式的大數加法，輸入、輸出的字串皆為反序的整數 */
    string bigAddRev(string s, string t) {
        string u;
        while(s.size() < t.size()) s += "0";
        while(s.size() > t.size()) t += "0";
        int n = (int)s.size(), carry = 0;
        for(int i = 0; i < n; i++) {
            int d = s[i] - '0' + t[i] - '0' + carry;
            u += char(d%10 + '0');
            carry = d / 10;
        }
        if (carry > 0) u += char(carry + '0');
        return u;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        /* 遍歷鏈結串列 l1, l2，讀取串列中儲存的反序整數 */
        string num1, num2;
        while(l1 != nullptr) {
            num1 += char(l1->val + '0');
            l1 = l1->next;
        }
        while(l2 != nullptr) {
            num2 += char(l2->val + '0');
            l2 = l2->next;
        }
        
        /* 呼叫自訂的大數加法函式計算加總，建一個新的鏈結串列儲存加總 */
        string isum = bigAddRev(num1, num2);
        ListNode* head = new ListNode(isum[0] - '0');
        int n = (int)isum.size();
        ListNode* dummy = head;
        for(int i = 1; i < n; i++) {
            dummy->next = new ListNode(isum[i] - '0');
            dummy = dummy->next;
        }
        return head;
    }
};

Runtime: 7 ms, beats 7.19%. Memory: 78.82 MB, beats 12.67%.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    /* 自訂函式，整數陣列格式的大數加法，輸入、輸出的陣列皆為反序的整數 */
    vector<int> bigAddRev(vector<int> a, vector<int> b) {
        vector<int> c;
        while(a.size() < b.size()) a.push_back(0);
        while(a.size() > b.size()) b.push_back(0);
        int n = (int)a.size(), carry = 0;
        for(int i = 0; i < n; i++) {
            int d = a[i] + b[i] + carry;
            c.push_back(d%10);
            carry = d / 10;
        }
        if (carry > 0) c.push_back(carry);
        return c;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        /* 遍歷鏈結串列 l1, l2，讀取串列中儲存的反序整數 */
        vector<int> num1, num2;
        while(l1 != nullptr) {
            num1.push_back(l1->val);
            l1 = l1->next;
        }
        while(l2 != nullptr) {
            num2.push_back(l2->val);
            l2 = l2->next;
        }
        
        /* 呼叫自訂的大數加法函式計算加總，建一個新的鏈結串列儲存加總 */
        auto isum = bigAddRev(num1, num2);
        ListNode* head = new ListNode(isum[0]);
        int n = (int)isum.size();
        ListNode* dummy = head;
        for(int i = 1; i < n; i++) {
            dummy->next = new ListNode(isum[i]);
            dummy = dummy->next;
        }
        return head;
    }
};