JavaScriptでLeetCodeを始めました~LinkedList編~[後編]

今日はTOEICの模擬試験を受けました！結果は、スコア換算で800点台といったところです。
一般的な企業では十分な指標かと思いますが、自分は将来的に海外企業で働きたいと考えていますので正直900点台を狙いたかったです…😭
とはいえ、これが今の自分の実力ですし、一歩一歩力をつけていくしかないですね！プログラミング同様に英語も頑張れば結果はついてくると思いますので、LeetCode同様英語勉強も頑張っていきたいです！💪
とはいえ、今のままコロナが続いていると秋以降のTOEIC試験開催も危ぶまれるので、コロナが収束されることだけはアッラーに祈っております…🙏
閑話休題、それでは今週は先週に続いてLinkedListの後編を紹介していきたいと思います！

Merge Two Sorted Lists

「2つのソート済のLinkedListが与えられる。これらをマージし、1つのソート済LinkedListにせよ」という問題です。
この問題のアプローチとして、まず空のdummyというオブジェクトを用意します。こちらにソート済みのLinkedListを格納していきます。また、その初期値をinitという変数に逃しておきます。これにより後々マージ済みLinkedListの先頭を参照することが出来ます。そして、while文を回します。while文は、いずれかのLinkedListが最後尾まで行ったところで抜ける条件にします。これは、いずれかが終わりまでいけば、残りはソート済なので最終的なマージLinkedListに残りを繋げるだけでOKだからですね。whileの中では、2つのLinkedListのheadをそれぞれ比較し、小さい方をdummy.nextに繋げ、LinkedList自体も進めます。これによりdummyに2つのNodeが小さい順に続いていき、最終的にはソート済のマージLinkedListになります！ただ、dummyはもう既にLinkedListが進んである状態なので、一番先頭のNodeであるinit.nextを返します。これで答えとなります！以下が実際に実装したコードになります。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
  if (l1 === null || l2 === null) {
    return l1 === null ? l2 : l1;
  }
  let dummy = {};
  const init = dummy;

  while (l1 !== null && l2 !== null) {
    if (l1.val > l2.val) {
      dummy.next = l2;
      l2 = l2.next;
    } else {
      dummy.next = l1;
      l1 = l1.next;
    }
    dummy = dummy.next;
  }
  if (l1 === null || l2 === null) {
    dummy.next = l1 === null ? l2 : l1;
  }
  return init.next;
};

結構シンプルにLinkedListの特性を活かして書けたのではないかと思います！
他の解答を見ても似たようなアプローチだったので、このような解き方に収束するのでしょうね！

Palindrome Linked List

Palindromeは以前も出ましたね！回文という意味です。なので、この問題は、「あるLinkedListが与えられた時、そのLinkedListが回文であるか判定せよ」という問題になります。ここでは、まず自分の解答を紹介したいと思います。以下のコードです！

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  if (head === null) {
    return true;
  }
  const arr = [];
  while (head !== null) {
    arr.push(head.val);
    head = head.next;
  }
  for (let index = 0; index < arr.length; index++) {
    if (arr[index] !== arr[arr.length - 1 - index]) {
      return false;
    }
  }
  // 文字列で評価すると若干メモリ消費が多くなる
  // if (arr.join("") === arr.reverse().join("")) {
  //   return true;
  // } else {
  //   return false;
  // }
  return true;
};

アルゴリズムは単純です！LinkedListをまずは最後まで回し、その中身をArrayに移します。そして、あとはArrayのreverse関数を用いてもいいですし、for文で回して配列の中身を確認してもOKです！いずれにせよArrayにすることで中身を逆からも確認できるようにすることで答えを導きます。

ただ、上記の解法は邪道です。前回も紹介しましたが、LinkedListの問題なのに結局Arrayに頼っています。これはイケてないですね…。なので、次に紹介する方法がスマートな解法かと思います！ちなみに自分で導き出したわけではなく、Solutionから参考にさせていただきました！

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  if (head === null) {
    return true;
  }

  let fast = head;
  let slow = head;
  // Slowは半分しか進んでいない = 後半部分の最初のNodeである
  while (fast && fast.next !== null) {
    fast = fast.next.next;
    slow = slow.next;
  }

  let prev = null;
  while (slow) {
    // 次のSlowを退避させる
    const next = slow.next;
    // prevは初期値でnullで、ここにslowの値を入れていく
    // slow.next = prev前回のslowの値がここに蓄積されていく
    // 結果として最終的にprevには後半の逆転した値が入っている
    slow.next = prev;
    prev = slow;
    slow = next;
  }

  let p1 = head;
  let p2 = prev;
  while (p2 !== null) {
    if (p1.val !== p2.val) {
      return false;
    }
    p1 = p1.next;
    p2 = p2.next;
  }

  return true;
};

解法のポイントとしては、まずheadをfastとslowという2つの変数に代入し、while文でfastがnullになるまでfastとslowを進めていきます。ここでfast だけ2つ飛ばしに進めます。これによりwhileを抜けた時に、slowはLinkedListはちょうど半分まで進んだ状態になります。
次に、slowをnullになるまでwhileで回します。ここでは、prevという初期値nullの変数を用意します。そして、slow.nextを退避させた状態でslow.nextにprevを代入します。続いてprevにslowを代入します。最後にslowに退避させておいた次のNodeを代入します。これにより何が起こるかと言いますと、prevには毎回slowの前回の値が入っていくのですね。そして、slow.nextにprevを代入するということは、現在のslowのNodeの次のNodeを前回のNodeにする。すなわち逆回転させているわけです！まとめますと、ここでは与えられたLinkedListの後半部分について逆転したLinkedListを作っているのです！
ここまで来るとあとは簡単です。逆転した後半部分について、nullになるまでLinkedListを回し、毎回LinkedListの先頭と比較を行っていき、もし値が異なれば回文ではないということでfalseを返し、後半部分が最後まで先頭から進めた場合と一緒であれば回文なのでtrueとなります。スマートなやり方ですね！解法としてはArrayも使えるは使えるのですが、やはりLinkedListの問題なのでLinkedListのみで答えるこのような解法を導いていきたく思います！

Linked List Cycle

LinkedListの最後は、「与えられたLinkedListがループを持つか否か判定せよ」という問題です。
自分の解法は以下のようになりました！

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  if (head === null) {
    return false;
  }
  const map = new Map();
  while (true) {
    if (head.next === null) {
      return false;
    }
    if (map.has(head)) {
      return true;
    }

    map.set(head);
    head = head.next;
  }
};

LinkedListを回していく中で、HashMapを確認し、もしも現在のNodeと同じものが過去に存在していればそれをループとしてみなすというものです。Solutionも第一にHashMapの解法が紹介されていましたので、ここらへんがまず思い浮かぶ方法なのかもしれません。ただ、HashMapはメモリ消費量も多くスピードも遅くなりがちです。なので、別の解法があるならばそれを試したくなります。そこで、Solutionを確認した所、Two Pointerという方法が紹介されていました。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  if (head == null || head.next === null) return false;
  let slow = head;
  let fast = head.next;

  while (slow != fast) {
    if (fast == null || fast.next === null) {
      return false;
    }
    fast = fast.next.next;
    slow = slow.next;
  }

  return true;
};

これは、fastとslowの2つのNodeを走らせます。fastは一回の移動で次の次のNodeに移ります。slowは、一回の移動で次のNodeに移ります。このようにして回っている時に、fastがnullを迎えると、nullを迎える = ループではないのでfalseとわかります。また、fastとslowはLinkedListがループの場合う、いつかfastがslowに追いついて同じNodeを指すようになります。そうなると、先に進んでいたはずのfastが同じNodeを指す = ループということが分かり、trueを返します。このTwo PointerであればHashMapを使っていないためメモリ消費量が少なくパフォーマンスにも優れます。勿論、答えが出ないよりは全然良いのでHashMapを用いたやり方も正しいとは思いますが、Two Pointerもしっかりと使えるように武器として持っておきたいなと思います。

まとめ

今回でLinkedListが終わりました！自分はこの後のMathまで進んでいるのですが、あとの章は問題数が少ないので、ここまでで半分まで終わった感覚ですね！LinkedList、後の章でも使い所が出てきたりして本当に面白いなと思います。Nodeで情報を持つのは便利が良いですし、この後にまとめるTreeとも相性が良さそうな感じがします。ここらへんを使って、探索するアルゴリズムを組めるようになると、LeetCodeのコンテストやAtCoderでももっと問題を解けるようになるのかなーっと思ったりもします。なかなか実務ではこれらのアルゴリズムを実装する機会がないので、今のところは自己満足ではあるのですが引き続き精進していきたいです！💪