JavaScriptでLeetCodeを始めました~LinkedList編~[前編] - ムスリムエンジニアbebetaroのブログ

本日のLeetCode Contestは鯖落ちによりunratedになりましたね。
ただ問題の中身を見てみると、結構自分が苦手なタイプの問題なので2完が良いところだったのではと思っています…😅 勉強してアルゴリズム力が身についてきているという実感はあるのですが、実践力はまだまだ発展途上ですね。

さて、今回からはLinkedList問題に取り組んでいこうと思います！ LinkedListはArrayのようなリストなのですが、一方向の情報しか持ちません。なので、真ん中のNodeの情報や逆戻りに探索するのが苦手なようです。しかし、一方向の情報探索ではArray以上に高速な探索を行えるようでして、ケース・バイ・ケースでパフォーマンスを意識できると実装に幅がでてきそうですね！それでは早速LinkedList問題を解いていこうと思います！

Delete Node in a Linked List
Remove Nth Node From End of List
Reverse Linked List
まとめ

Delete Node in a Linked List

LinkedListとはなんぞや？を理解するのはこの問題が適当ですね！「あるLinkedListがある。その中から1つNodeを渡された時、そのNodeをLinkedListから削除せよ」という問題です。LinkedListでは、それぞれのNodeは①自分の値と②次のNodeの情報しか持ちません。なので、LinkedListでは、そのNodeの順番は考慮する必要がありません。むしろ順番を考慮せずパフォーマンスを発揮する点にLinkedListのメリットが表れています。それらを考慮して問題を解くと以下のようになります。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function (node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

非常にシンプルですね！
受け取ったNodeのvalとnextを自身が情報として持つnextのvalとnextでアップデートしています。ここで需要なのは、先程も述べたNodeが持っているのは自身の値と次の値のみという点です。つまり、引数として渡ってきたNodeの前に何があろうとNodeは気にする必要はありませんし、気にする手立てもありません。なので無視します。また、自身をNodeの次のNodeでアップデートしたそれ以後のNodeについても、それはその後のNodeが情報として持っているので気にする必要はありません。これがLinkedListのポイントですね！
ということで、LinkedListは次々とnextを参照して移動していく。そして移動した先が変更されたとしても、他のNodeは感知する術がないので、粛々とnextを参照して移動していきます。これを利用してnodeのvalとnextを上記のようにアップデートすることでこのNodeに参照が渡ってきた時にアップデートされた値で参照されるため、nextのvalを参照してnextのnextに移っていきます。すなわち、参照から外してLinkedListのnextの参照先にならないことで削除が実現するのです。

Remove Nth Node From End of List

「LinkedListの先頭と数字nを受け取り、LinkedListの最後からn番目のNodeを削除せよ」という問題です。
自分は、Nodeを一つずつ進めていき、毎回のNodeでまたn番目先まで進める。もしn番目が最後のNodeであれば、それが削除すべきNodeとして次のNodeのvalとnextを割り当てる。また、n=1、すなわち最後のNodeを削除する時は、その一つ前のNodeでnextをnullとするという処理にしました。これをコードに直したものが以下になります。

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

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */

const removeNode = (head, n) => {
  if (n === 1 && head.next.next === null) {
    head.next = null;
    return;
  }
  if (findNode(head, n - 1)) {
    if (head.next) {
      head.val = head.next.val;
      head.next = head.next.next;
    }
    return;
  }
  return removeNode(head.next, n);
};

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {boolean}
 */
const findNode = (head, n) => {
  if (n === 0) {
    return head.next === null ? true : false;
  }
  return findNode(head.next, n - 1);
};

removeNode関数とfindNode関数を作成し、再帰的にNodeの走査を行います。findNodeは現在のheadとnを受け取り、n分進めた時に最後のNode、すなわち最初に与えられたheadが最後からn番目のNodeである時にtrueを、それ以外でfalseを返します。removeNodeは、Nodeを1つずつ進めていき各NodeでfindNode関数を回します。もしfindNodeからtrueが返ってくれば、これが最後のNodeからn番目としてそのNodeを削除します。
このようなアルゴリズムで進めました。ただ、扱う関数が多く冗長的な感じがします。そこで、Solutionを参照した所、以下のような解法が見つかりました！

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
const removeNthFromEnd = (head, n) => {
  const dummy = {};
  dummy.next = head;
  let length = 0;
  let first = head;
  while (first != null) {
    length++;
    first = first.next;
  }
  // 全体の長さからn分だけ差し引く
  length -= n;
  // firstにdummyを入れる
  first = dummy;
  while (length > 0) {
    length--;
    // dummyからスタートするので除去すべき値の一つ前まで進める
    first = first.next;
  }
  // first.nextで除去すべきNodeにその次のNodeを差し込んでいる
  first.next = first.next.next;
  // 一番最初のNodeを返す
  return dummy.next;
};

まず空っぽのdummyオブジェクトを作り、そのnextに最初のnodeを代入します。このdummyオブジェクトのおかげで自分の解法のような冗長的な再帰が解消されています。そして、length変数にwhileを用いてLinkedListの長さを代入していきます。全ての長さがわかった後にlengthからnを引きます。ここもスマートです！これのおかげで自動的にその後のwhileは最後からn番目の削除すべきNodeの1つ前までしか進まなくなります。(空オブジェクトであるdummyからスタートしているので、1つ前までとなる)また、lengthを調べる時に用いたfirstにその後dummyを代入することで変数を上手く再利用もしていますし、これによりwhileを一度も回さないパターン、すなわち最初のNodeを削除するパターンにも対応できています。これらによりfirstには削除すべきNodeの1つ前のNodeが入っているため、それを飛ばすようにfirst.next = first.next.nextを代入し、一番最初のNodeを返すためにdummy.nextを返すと答えが導けます。無駄な変数を極力減らし、条件分岐もないスマートな解法ですね！

Reverse Linked List

「与えられたLinkedListを逆向きのLinkedListにせよ」という問題です。Arrayであればreverseを用いれば簡単に実行できますが、LinkedListは自分の値と次のNodeしか知らないため難しいです。この問題、自分は解くためにArrayを併用しました。ただ、これは邪道かと思いますので、この次に紹介する方法を参照して下さい。あくまで以下は参考程度です。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  if (head === null) {
    return head;
  }
  const arr = [];
  while (head.next !== null) {
    arr.push(head);
    head = head.next;
  }
  arr.push(head);
  arr.reverse();
  for (let index = 0; index < arr.length; index++) {
    head.next = arr[index + 1];
    head = head.next;
  }
  return arr[0];
};

whileによりheadを最後まで回していき、都度Arrayに順番にNodeを差し込んでいきます。headを最後まで回していったので、現在のheadは最後の値、すなわち逆向き後の最初の値になっています。そして、Arrayをreverseにより逆向きにした後にfor文を回して、head.nextにarrayの次の値を入れていきます。イメージとしては、最初のwhileで最後まで行ったLinkedListに逆向きにした値を追加していく感じです。こうすることで、ReversedなLinkedListが作られます。関数から消す値は、Arrayの一番最初の値を返せば参照する範囲はreverse後のLinkedListのみとなります。
これで答えは出ますが、せっかくLinkedListを用いているのにArrayを使うのはなんだか勿体ないですね。そこで、Arrayを用いない方法を探してみた所、以下のような解法がありました！

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const reverseList = (head) => {
  if (head == null || head.next == null) return head;
  // pには最後のnodeが入っている
  const p = reverseList(head.next);
  // このノードの次のノードのnextに差し込む
  //イメージとしては、[1,2,3]を[3,2,1]と逆転するのではなく、
  // 2の次は3、3の次に2を差し込む、1の次は2で2の次に1を差し込む処理が以下
  head.next.next = head;
  head.next = null;
  return p;
};

まず、再帰を進めていき最後のnodeまで辿り着くと最後のnodeを返し、それをpに返します。以後、再帰は全てpを返すので当初の最後の値、すなわちreverse後の最初の値がreverseListの返り値してここで確保されます。また、

  head.next.next = head;
  head.next = null;

この部分ですが、例えば[1,2,3,4,5]のLinkedListの時最後の値である5がpに入り、headには4が入るとします。head.nextは5ですね？そして、head.next.nextは5が最後の値であるためnullです。そこにhead.next.next = headとして4が入ると、[5, 4...]となります。また、4の次は5でしたが、head.next = nullで初期化します。次に再帰関数で戻るため、headには3が入ります。head.next.nextは当初であれば、4の次であるため5でしたが、その直前にhead.next.next = headにより3となります。ここでピンと来ますね。各headには次の値であるhead.nextの情報があります。そして、今は逆向き後であるためhead.nextが自身のNodeの前を表すようになります。すなわち、head.next.nextは現在headであるNodeそのものを指すようになるためhead.next.next = headにより再帰が戻っていく中で次々と逆向きのnextが完成していくのです。そして、最後の1はその後のheadがないため、head.next = nullとなりLinkeListの終わりもキッチリと締められます。スマートですね！このような無駄のない再帰関数は惚れ惚れします。自分の解法も元々の最終端後を拡張するという点はうまくできたのですが、next部分の再帰的な処理が上手くいかずArrayの機能を使わざるを得ませんでした。ここをしっかりとLinkedListの構造をマスターすることで、Arrayに頼らず解答できるように精進を重ねていきたいですね！

まとめ

LinkedListの前編が終わりました！ここまではまだまだLinkedListの基礎って感じなのですかね。それでもArrayとは異なり、Listの構造を意識する必要があり、なかなか難しいです😅思うに、nextがLinkedListの肝になっていそうなので、このnextを上手く使いこなせればもっと表現の幅が広がりそうです。なかなか難易度は高いですが、同時に面白さと可能性も感じます。また、難易度が高ければ高いほど、習得したときの成長幅は大きいと思いますので、引き続きLinkedListを頑張っていきたいと思います！💪