JavaScriptでリンクリスト（連結リスト）の中央ノードを見つける方法

問題概要

連結リストの先頭ノード（head）を唯一の引数として受け取るJavaScript関数を作成することを考えます。

この関数は、リストの中央に位置するノードに格納されている値を返す必要があります。もし中央にあたるノードが2つ存在する場合（ノード数が偶数の場合）は、そのうち後ろ側（2番目）のノードの値を返します。

たとえば、次のようなリストが与えられた場合を考えてみましょう。

入力例

[4, 6, 8, 9, 1]

出力例

const output = 8;

5つのノードがあるため、中央は3番目のノード「8」になります。

実装コード例

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    };
};
class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    };
};
LinkedList.prototype.add = function(data) {
    const newNode = new Node(data);
    let curr;
    if(this.head === null) {
        this.head = newNode;
    } else {
        curr = this.head;
        while(curr.next) {
            curr = curr.next;
        }
        curr.next = newNode;
    };
    this.size++;
};
const list = new LinkedList();
list.add(4);
list.add(6);
list.add(8);
list.add(9);
list.add(1);
const findMiddle = (head) => {
    let slow = head
    let fast = head
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow.data
};
console.log(findMiddle(list.head));

実行結果

8

解法のポイント：「低速・高速ポインタ」テクニック

上記のコードで使われているのは、フロイドの循環検出法（ウサギとカメのアルゴリズム）としても知られる、2つのポインタを使った有名な手法です。

• slowポインタ：1回のループごとに1ノードだけ進みます。
• fastポインタ：1回のループごとに2ノードずつ進みます。

fastポインタがリストの終端に到達したとき、slowポインタはちょうど半分の距離、つまりリストの中央に到達しています。この性質により、リスト全体の長さを事前に計算しておく必要がありません。

処理の流れ

1. slowとfastの両方を先頭ノードで初期化します。
2. fastおよびfast.nextが存在する間、ループを続けます。
3. 各ループでslowを1つ、fastを2つ進めます。
4. ループ終了時、slowが指しているノードが中央のノードです。

計算量

• 時間計算量：O(n) ― リストを一度走査するだけで済みます。
• 空間計算量：O(1) ― 追加の配列やデータ構造は不要です。

なお、ノード数が偶数の場合でも、このループ条件ではslowが自動的に「2つの中央ノードのうち後ろ側」に停止するため、追加の判定なしに要件を満たせます。