【アルゴリズム】JavaScriptで連結リスト問題を解く

#はじめに
Qiitaの競技プログラミング研究月間ということで、アルゴリズムの記事を書いています。
今回は連結リスト問題をまとめました。

JavaScriptでアルゴリズムの勉強をされている方の参考になれば幸いです。
記事を順次まとめていきますので、その他の記事についてはマイページからご覧ください。

https://qiita.com/suzuki0430

https://qiita.com/official-events/5a0502a2d94ed6a00c30

#連結リスト
連結リストを構成する、NodeクラスとLinkedListクラスを作成してください。

Nodeクラスのインスタンスプロパティにはdataとnextをもってください。
nextには連結先のノードのデータをもち、連結先がなければnullを返してください。

LinkedListクラスのインスタンスプロパティにはheadをもってください。
headには連結リストの最初のノードのデータを持ち、デフォルトではnullとなります。
また、LinkedListクラスは連結リストを操作する複数のメソッドをもちます。
![スクリーンショット 2021-06-17 21.53.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/569054/dfab2007-a10c-1d3b-751e-6a2cb372ee43.png)

##解答
解答は以下のようになります。
メソッドの役割はノードの追加・削除・取得にわけられ、後は連結リストのどの位置で実行するかどうかの違いとなります。
メソッドを作成する上で、操作するノードがどのノードに連結されるかどうかを意識するのがとても重要です。

```js:index.js
class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  // 先頭にノードを追加
  insertFirst(data) {
    this.insertAt(data, 0)
  }

  // 全ノード数を取得
  size() {
    let counter = 0;
    let node = this.head;

    while (node) {
      counter++;
      node = node.next;
    }

    return counter;
  }

  // 先頭のノードを取得
  getFirst() {
    return this.getAt(0)
  }

  // 最後のノードを取得
  getLast() {
    return this.getAt(this.size() - 1)
  }

  // 全ノードを削除
  clear() {
    this.head = null;
  }

  // 先頭のノードを削除
  removeFirst() {
    if (!this.head) {
      return;
    }

    this.head = this.head.next;
  }

  // 最後のノードを削除
  removeLast() {
    // ノードがないとき
    if (!this.head) {
      return;
    }

    // ノードが一つしかないとき
    if (!this.head.next) {
      this.head = null;
      return;
    }

    // ノードが二つ以上のとき
    let previous = this.head;
    let node = this.head.next;

    // previous, nodeを一個ずつずらす
    while (node.next) {
      previous = node;
      node = node.next;
    }
    previous.next = null;
  }

  // 最後にノードを追加
  insertLast() {
    const last = this.getLast();

    if (last) {
      last.next = new Node(data);
    } else {
      this.head = new Node(data);
    }
  }

  // 指定したノードを取得
  getAt(index) {
    if (!this.head) {
      return null;
    }

    let counter = 0;
    let node = this.head;
    while (node) {
      if (counter === index) {
        return node;
      }

      counter++;
      node = node.next;
    }
    return null;
  }

  // 指定したノードを削除
  removeAt(index) {
    if (!this.head) {
      return;
    }

    if (index === 0) {
      this.head = this.head.next;
      return;
    }

    //　一個前のノードの連結先を変える
    const previous = this.getAt(index - 1);
    if (!previous || !previous.next) {
      return;
    }
    previous.next = previous.next.next;
  }

  // 指定位置へのノードの挿入
  insertAt(data, index) {
    if (!this.head) {
      this.head = new Node(data);
      return;
    }

    if (index === 0) {
      this.head = new Node(data, this.head); // 前のheadをnextにする
      return;
    }

    const previous = this.getAt(index - 1) || this.getLast();
    previous.next = new Node(data, previous.next);
  }
}
```
###ノードの取得
指定した位置のノードを取得するメソッド`getAt()`は以下のようになります。
まず、headが存在しなければnullを返します。
headが存在していれば`let node = this.head`で`node`を定義し、while内で`counter`の値と同時に`node`の位置を`node = node.next`で移動させます。
そして、`counter`と`index`の値が一致したら`node`を返すようにします。

```js
  getAt(index) {
    if (!this.head) {
      return null;
    }

    let counter = 0;
    let node = this.head;
    while (node) {
      if (counter === index) {
        return node;
      }

      counter++;
      node = node.next;
    }
    return null;
  }
```

###ノードの追加
指定した位置にノードを追加するメソッド`insertAt()`は以下のようになります。
headが存在しなければ、`this.head = new Node(data)`でheadに直接ノードを作成します。
先頭(index = 0)にノードを作成するときは、`this.head = new Node(data, this.head)`として新しいノードを作成してheadの更新も行います。
また、指定したindex、またはリストの最後にノードを追加する場合には、`const previous = this.getAt(index - 1) || this.getLast()`で追加したい位置の前のノード`previous`を取得します。
`||`の演算子を使うことで、`this.getAt(index - 1)`のノードが存在しない場合に、`this.getLast()`で最後のノードを取得することができます。
最後に`previous.next = new Node(data, previous.next)`とすることで、ノードの矢印の向きを更新します。

```js
  insertAt(data, index) {
    // 空のリストにノードを追加する場合
    if (!this.head) {
      this.head = new Node(data);
      return;
    }

    // 先頭にノードを追加する場合
    if (index === 0) {
      this.head = new Node(data, this.head); // 前のheadをnextにする
      return;
    }

    // リストの中、最後にノードを追加する場合
    const previous = this.getAt(index - 1) || this.getLast();
    previous.next = new Node(data, previous.next);
  }
```

###ノードの削除
最後のノードを削除するメソッド`removeLast()`は以下のようになります。
削除したいノード`node`とその一個前のノード`previous`を用意して、これらを`node.next`がnullになるまで`while (node.next)`で更新していきます。
最後のノード`node`が見つかったところで、`previous`の連結先`previous.next`をnullにしてあげれば削除完了です。

```js
  removeLast() {
    // ノードがないとき
    if (!this.head) {
      return;
    }

    // ノードが一つしかないとき
    if (!this.head.next) {
      this.head = null;
      return;
    }

    // ノードが二つ以上のとき
    let previous = this.head;
    let node = this.head.next;

    // previous, nodeを一個ずつずらす
    while (node.next) {
      previous = node;
      node = node.next;
    }
    previous.next = null;
  }
```

また、指定したノードを削除するメソッド`removeAt()`は以下のようになります。
こちらについても削除したいノードの一個前のノード`previous`に着目し、連結先を変えるような操作`previous.next = previous.next.next`を行います。

```js
  removeAt(index) {
    // ノードが空の場合
    if (!this.head) {
      return;
    }

    // 先頭のノードを指定した場合
    if (index === 0) {
      this.head = this.head.next;
      return;
    }

    // 上記以外の場合
    // 一個前のノードpreviousの連結先を変える
    const previous = this.getAt(index - 1);
    if (!previous || !previous.next) {
      return;
    }
    previous.next = previous.next.next;
  }
```

#中心ノード探索
連結リストの中心のノードを返してください。
ノードの数が偶数の場合は、リストの前半分の最後のノードを返してください。
＊counter変数やsize()メソッドを利用しないでください。
＊繰り返しは1回まで許容されます。

```
const l = new LinkedList();
  l.insertLast('a')
  l.insertLast('b')
  l.insertLast('c')
  midpoint(l); // returns { data: 'b' }
```

##解答
初期値が先頭のノードである`slow`と`fast`という変数を用意し、`fast.next`と`fast.next.next`がnullになるまで、`slow`は1個、`fast`は2個ずつノードを更新していきます。
最終的な`slow`の値がリストの中心ノードとなります。

![スクリーンショット 2021-06-18 7.35.35.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/569054/601689cc-d209-423e-a8ea-1675b9afbcc0.png)

```js:index.js
function midpoint(list) {
  let slow = list.getFirst();
  let fast = list.getFirst();

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}
```

#リスト循環(Circular)
連結リストを引数に与えたときに、リストの一部が循環していたらtrue、循環していなければfalseを返してください。

```
  const l = new List();
  const a = new Node('a');
  const b = new Node('b');
  const c = new Node('c');
  l.head = a;
  a.next = b;
  b.next = c;
  c.next = b;
  circular(l) // true
```

##解答
中心ノード探索と解き方の方針は同じです。
リストが循環していると`slow`と`fast`が重なるので、そのときにtrueを返すようにします。

```js:index.js
function circular(list) {
  let slow = list.getFirst();
  let fast = list.getFirst();

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }
  return false;
}
```

#最後からn番目のノード探索
連結リストと整数nを引数に与えたときに、最後からn番目のノードを返してください。
＊size()メソッドは使用しないでください。
＊nは常にリストの長さ以下であると仮定してください。

```
   const list = new List();
   list.insertLast('a');
   list.insertLast('b');
   list.insertLast('c');
   list.insertLast('d');
   fromLast(list, 2).data // 'b'
```

##解答
中心ノード探索やリスト循環と同様に、先頭ノードを初期値とした`slow`と`fast`を用意します。
次に、`while (n > 0)`内で`fast`を更新し、`slow`とn個分間隔を空けます。
`while (fast.next)`で`slow`と`fast`を1個ずつ更新していき、`fast.next`がnullになったとき(`fast`が最後のノードになったとき)の`slow`を結果として返します。

```js:index.js
function fromLast(list, n) {
  let slow = list.getFirst();
  let fast = list.getFirst();

  // 最初にfastをn移動させる(slowをn個分間隔をあける)
  while (n > 0) {
    fast = fast.next;
    n--;
  }

  while (fast.next) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow;
}
```

#参考資料
https://www.udemy.com/share/101WNkCEEZd11VRno=/