Zenn
Open1

Leet Codeの2. Add Two Numbersの再帰を使った最もシンプルな方法

TypeScript
LeetCode
再帰
Nakano as a ServiceNakano as a Service

他の人の解法にはcarryが使われていたが、実は無くてもよいというか、こっちの方が素直。

  1. どちらかがnullのとき
    • nullでない方を返す
    • S(3→4→x, x) = 3→4→x
    • S(x, 5→x) = 5→x
  2. 1桁目同士を足した結果が10未満のとき
    • S(4→3→x, 5→4→x) = 9→S(3→x, 4→x)
  3. 1桁目同士を足した結果が10以上のとき
    • S(4→3→x, 8→4→x) = (12 % 10)→S(1->x, S(3→x, 4→x))
interface ListNode {
  val: number;
  next: ListNode | null;
}

function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null,
): ListNode | null {
  if (l1 && l2) {
    const sum = l1.val + l2.val;
    if (sum < 10) {
      return {
        val: sum,
        next: addTwoNumbers(l1.next, l2.next),
      };
    }

    return {
      val: sum % 10,
      next: addTwoNumbers(
        { val: 1, next: null },
        addTwoNumbers(l1.next, l2.next),
      ),
    };
  }

  return l1 || l2;
}