C++でLeetCodeの「Add two numbers」問題を解く

Problem

https://leetcode.com/problems/add-two-numbers/description/

Answer

/**
 * 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:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0; 

        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }
            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next; 

まず、期待される出力を考えてみよう。

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

l1とl2の数字を順番に合計すれば出力が得られる。

2 + 5 = 7
4 + 6 = 10 -> 0 // 4 + 6 = 10. 次の桁に1を運び、残りの桁を切り捨てる。
3 + 4 = 7 -> 7 + 1 = 8 // 前の桁から繰り越した1を加える。

Output: 7, 0, 8

次に、この操作をコードで表す必要がある。

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0; 

関数の結果は ListNode* なので、dummy を ListNode* 型の変数として定義する。 各桁を合計するために各ノードを参照する必要があるので、dummy ポインタを参照するために temp 変数を定義する。 carry`変数を定義して、繰り越された数値を格納する。

        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }

全ての l1 と l2 の数値を計算する必要がある。 つまり、 l1 と l2 が NULL で carry が 0 になるまで計算を続けなければならない。

もし l1 が NULL でなければ、l1 の値を sum 変数に加える。 現在の l1 の値は計算済みなので、l1 ポインタを次のポインタに移動する。

同じことを l2 にも行う。

            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next; 

前の桁から carry がある場合は、それを sum 変数に追加し、次の桁に繰り越す必要がある新しい値で carry を更新する必要がある。

sumの最初の桁を新しいNodeに代入し、この新しいNodeを temp->next に代入する。 これは新しい Node を dummy の ListNode に追加するが、新しい Node を直接 dummy->next に代入しない。

なぜなら dummy と temp は同じポインタを持っているからだ。 この理由は、関数の最後で新しい ListNode の先頭を返す必要があるからである。

temp は l1 と l2 を計算するためのポインタであり、dummy は新しい ListNode の先頭を返すためのポインタである。

本記事は英語から日本語に翻訳しています。 dev.to