二つの非空連結リストが与えられます。各リストは非負整数を逆順で表現し、各ノードは一桁の数字を保持します。二つの数を加算し、同じ形式で結果を返してください。両数値は先頭が0でないことが保証されます。

解法の要点

• 桁ごとの加算と繰り上がりの処理
• 仮想ヘッドノードによる実装の簡略化
• 異なる長さのリストへの対応

#include <iostream>

struct Node {
    int value;
    Node* next;
    Node() : value(0), next(nullptr) {}
    Node(int v) : value(v), next(nullptr) {}
    Node(int v, Node* n) : value(v), next(n) {}
};

class ListCalculator {
public:
    Node* sumLists(Node* listA, Node* listB) {
        Node* dummyHead = new Node(0);
        Node* current = dummyHead;
        int carry = 0;
        
        while (listA || listB || carry) {
            int valA = listA ? listA->value : 0;
            int valB = listB ? listB->value : 0;
            
            int total = valA + valB + carry;
            carry = total / 10;
            
            current->next = new Node(total % 10);
            current = current->next;
            
            if (listA) listA = listA->next;
            if (listB) listB = listB->next;
        }
        
        return dummyHead->next;
    }
};

// テストケース
int main() {
    // 123: 3→2→1
    Node* num1 = new Node(3);
    num1->next = new Node(2);
    num1->next->next = new Node(1);
    
    // 456: 6→5→4
    Node* num2 = new Node(6);
    num2->next = new Node(5);
    num2->next->next = new Node(4);
    
    ListCalculator calc;
    Node* result = calc.sumLists(num1, num2);
    
    // 出力: 9→7→5 (579=123+456)
    while (result) {
        std::cout << result->value << " ";
        result = result->next;
    }
    return 0;
}

実装の詳細

仮想ヘッドノードを使用することで、特殊な空リストケースの処理を回避できます。繰り上がり値は各桁計算時に更新され、両リストの終端後も継続して処理されます。

時間計算量: O(max(n,m))
空間計算量: O(max(n,m))