💨

LeetCode 2020-11-07: Add Two Numbers II

2020/11/10に公開

Java

LeetCode

tech

LeetCode の daily challenge Add Two Numbers II (medium) の挑戦メモです。

問題の概要

入力として二つの連結リストが与えられる
それぞれの連結リストは数値を表現している
- リストの先頭のノードが最上位桁の数値を表す
- 各ノードは 0 から 9 までのいずれかの値を保持する
これら二つの連結リストが表す数値を足し合わせ、結果を新たな連結リストで表現する
Follow up
- 入力として与えられる連結リストに 手を加えず に答えを求めること

考え方

Follow up を考えなければ、それぞれの連結リストを前後反転したのちにキャリーを考慮しつつ一桁ずつ足し上げていく ようにすれば容易に解けますね
入力の連結リストを変更しない方法としては、例えば以下の方法が考えられますね
1. 入力として与えられた連結リストのうち、連結リスト l1 をもとにそれを逆順にした 新たなリスト revL1 を構築する
2. 入力として与えられたもう一方の連結リスト l2 を、再帰を用いて逆順にたどりつつ以下の処理をする
  - 再帰によって到達した l2 の末尾から逆順に、revL1 の先頭から末尾に向かって一桁ずつキャリー有りで足し上げていく
  - このとき、revL1 のリストのノードをいま一度逆順に並べる (逆順の逆順になるので正順になる)
3. l1 と l2 の長さが異なる場合の処理をいい感じにやる
この方法で実装をして submit → 一発 accept 👍
- Runtime 2ms で Your runtime beats 98.98 % of java submissions.
分岐を削ってみたり色々工夫してみたが、1ms 到達は果たせず残念 😓

コード

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // l1 をもとに、その前後を反転させた連結リストを新たに作る (l1 そのものは一切弄らない)
        // 変数 revL1 はダミーノードであり、単に前後反転させた l1 の先頭ノードを保持するためだけに使っている
        ListNode revL1 = new ListNode();
        for (ListNode l1node = l1; l1node != null; l1node = l1node.next) {
            revL1.next = new ListNode(l1node.val, revL1.next);
        }

        // 再帰によって l2 を末尾から先頭の方向にたどりつつ、l1 を反転させたリストの各ノードに数値を加えていく
        // l1 を反転させたリストを再び反転し、元の順に戻したリストの先頭をダミーノードの result で保持する
        ListNode result = new ListNode();
        int carry = addRecursive(revL1, result, l2);

        // l1 のリストの方が長い場合、revL1 に処理されていないノードが残っているので、
        // キャリーを考慮しつつ処理していく
        while (revL1.next != null) {
            ListNode node = revL1.next;

            revL1.next = node.next;
            node.next = result.next;
            result.next = node;

            node.val += carry;
            carry = node.val / 10;
            node.val -= carry * 10;
        }

        // l1/l2 ともに処理を終えた時点でキャリーが残っていれば、新たにノードを先頭に加える必要がある
        if (carry == 1) {
            result.next = new ListNode(carry, result.next);
        }

        return result.next;
    }

    int addRecursive(ListNode revL1, ListNode result, ListNode l2) {
        if (l2 == null) {
            return 0;
        }

        // 先に再帰して、l2 のリストの末尾から順に加算を行っていく
        // キャリーが戻り値として得られる
        int carry = addRecursive(revL1, result, l2.next);

        ListNode node = revL1.next;
        if (node == null) {
            // l2 のリストの方が長い場合は、反転した l1 のリストのノードが足りなくなるので
            // ここで補充する
            node = new ListNode();
        }

        revL1.next = node.next;
        node.next = result.next;
        result.next = node;

        node.val += l2.val + carry;
        carry = node.val / 10;
        node.val -= carry * 10;

        return carry;
    }
}

問題の概要

考え方

コード

Discussion