Breathnote
LeetCodeの「Add-Two-Numbers」をJavaScriptで解く

LeetCodeの「Add-Two-Numbers」をJavaScriptで解く

JavaScriptで解くLeetCodeシリーズ。

第2回は、連結リストが登場する「Add-Two-Numbers」という問題を紹介します。

問題

自然数を1桁ごとに格納した連結リストが2つ与えられたとき、その連結リストが表す自然数同士を加算した連結リストを返却する。ただし自然数は逆順で格納されており、返却する連結リストも逆順でなければならない。なお、連結リストの最終ノードに0が与えられることはない。

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

解法

Solutionの中でも人気だった、再帰処理を用いた解答例を紹介します。

JavaScript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

var addTwoNumbers = function(l1, l2) {
  let node = null
  const carry = arguments[2]

  if (l1 || l2) {
    const val1 = l1 ? l1.val : 0
    const val2 = l2 ? l2.val : 0
    const next1 = l1 ? l1.next : null
    const next2 = l2 ? l2.next : null
    const val = carry ? val1 + val2 + 1 : val1 + val2
    node = new ListNode(val % 10)
    node.next = addTwoNumbers(next1, next2, val >= 10)
  } else if (carry) {
    node = new ListNode(1)
  }

  return node
};

三項演算子のおかげで、再帰呼び出し時の分岐処理が分かりやすくなっており、else ifで最終桁の繰り上がりも考慮されています。繰り上がりの有無をarguments[2]で受け取っている部分がスマートですね。

所感

私もこんなコードがスッと書けるようになりたい…。