はじめに

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

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

連結リスト

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

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

LinkedListクラスのインスタンスプロパティにはheadをもってください。
headには連結リストの最初のノードのデータを持ち、デフォルトではnullとなります。
また、LinkedListクラスは連結リストを操作する複数のメソッドをもちます。

解答

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

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を返すようにします。

  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)とすることで、ノードの矢印の向きを更新します。

  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にしてあげれば削除完了です。

  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を行います。

  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の値がリストの中心ノードとなります。

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を返すようにします。

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を結果として返します。

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;
}

参考資料