C++で連結リストの中央ノードを削除する方法

このチュートリアルでは、C++を使って連結リスト（リンクリスト）の中央にあるノードを削除する方法を解説します。

この問題の解き方は非常にシンプルです。2つのポインタを用意し、一方は1ノードずつ、もう一方は2ノードずつ進めます。速い方のポインタが連結リストの末尾に到達したとき、遅い方のポインタはちょうど中央に位置することになります。これは「フロイドの循環検出法」などでも使われる有名なテクニックで、リストの長さを事前に計算する必要がないのがポイントです。

それでは、問題を解くための手順を順番に確認していきましょう。

• 連結リストのノード用に構造体 Node を定義します。

• ダミーデータで連結リストを初期化します。

• 中央ノードを削除する関数を作成します。

  • 低速ポインタ（slow_ptr）と高速ポインタ（fast_ptr）を、連結リストの先頭ポインタで初期化します。

  • 高速ポインタが末尾に到達するまで連結リストを走査します。

  • 低速ポインタを次のノードへ1つ進めます。

  • 高速ポインタを2つ先のノードへ進めます。

  • 先頭ポインタを返します。

• 連結リストを出力して結果を確認します。

サンプルコード

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
struct Node* deleteMiddleNode(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->next == NULL) {
        delete head;
        return NULL;
    }
    struct Node* slow_ptr = head;
    struct Node* fast_ptr = head;
    struct Node* prev;
    while (fast_ptr != NULL && fast_ptr->next != NULL) {
        fast_ptr = fast_ptr->next->next;
        prev = slow_ptr;
        slow_ptr = slow_ptr->next;
    }
    prev->next = slow_ptr->next;
    delete slow_ptr;
    return head;
}
void printLinkedList(struct Node* node) {
    while (node != NULL) {
        cout << node->data << " -> ";
        node = node->next;
    }
    cout << "Null" << endl;
}
Node* newNode(int data) {
    struct Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
int main() {
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    cout << "Linked list before deleting middle node: ";
    printLinkedList(head);
    head = deleteMiddleNode(head);
    cout << "Linked List after deleting middle node: ";
    printLinkedList(head);
    return 0;
}

実行結果

上記のプログラムを実行すると、以下のような出力が得られます。6つのノードを持つ連結リストから、中央にあたる「4」が削除されていることが確認できます。

Linked list before deleting middle node: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> Null
Linked List after deleting middle node: 1 -> 2 -> 3 -> 5 -> 6 -> Null

まとめ

このチュートリアルでは、低速・高速の2つのポインタを活用することで、リストの長さを事前に求めなくても、時間計算量 O(n)・空間計算量 O(1) で中央ノードを効率的に削除できることを学びました。単一方向の連結リストしか扱えない場面でも応用できる重要なテクニックなので、ぜひマスターしておきましょう。

このチュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。