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

本記事では、C++を使って単方向連結リスト（Singly Linked List）の中央にあるノードを削除する方法を解説します。まずは基本となるノード構造体の定義から始め、ノード生成・削除・表示のための各関数を実装していきましょう。

1. ノード構造体の定義

最初に、データ（data）と次のノードへのポインタ（next）を持つ連結リストのノードを定義します。

struct Node {
    int data;
    struct Node* next;
};

2. ノードを生成する createNode 関数

次に、createNode(int data) 関数を作成します。この関数は int 型の data を引数として受け取り、その値を新しいノードに代入したうえで返します。新しく作成されたノードの next ポインタは NULL で初期化されます。

Node* createNode(int data){
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

3. 中央ノードを削除する deleteMiddle 関数

ここが本記事の核心となる deleteMiddle(struct Node* head) 関数です。引数としてリストの先頭ノードを受け取ります。

処理の流れは以下のとおりです。

• 先頭ノードが NULL の場合、何もせず NULL を返します。
• ノードが1つしかない場合、そのノードを削除して NULL を返します。
• それ以外の場合は、まず nodeCount() でノード総数を数え、中央位置（count / 2）までポインタを進めます。
• 中央ノードの「前のノード」の next を「中央ノードの次のノード」に付け替えることで、中央ノードをリストから外します。
• 最後に、変更後の先頭ノード temphead を返します。

struct Node* deleteMiddle(struct Node* head){
    if (head == NULL)
        return NULL;
    if (head->next == NULL) {
        delete head;
        return NULL;
    }
    Node* temphead = head;
    int count = nodeCount(head);
    int mid = count / 2;
    while (mid-- > 1) {
        head = head->next;
    }
    head->next = head->next->next;
    return temphead;
}

なお、ノード数をカウントする補助関数 nodeCount() は次のように実装します。

int nodeCount(struct Node* head){
    int count = 0;
    while (head != NULL) {
        head = head->next;
        count++;
    }
    return count;
}

4. リストを表示する printList 関数

最後に、リストの先頭ノードを受け取って全ノードの値を順に出力する printList(Node *ptr) 関数を用意します。

void printList(Node * ptr){
    while (ptr!= NULL) {
        cout << ptr->data << "->";
        ptr = ptr->next;
    }
    cout << "NULL"<<endl;
}

完全なサンプルコード

それでは、単方向連結リストの中央を削除する一連の実装をまとめて確認してみましょう。

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
Node* createNode(int data){
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
int nodeCount(struct Node* head){
    int count = 0;
    while (head != NULL) {
        head = head->next;
        count++;
    }
    return count;
}
struct Node* deleteMiddle(struct Node* head){
    if (head == NULL)
        return NULL;
    if (head->next == NULL) {
        delete head;
        return NULL;
    }
    Node* temphead = head;
    int count = nodeCount(head);
    int mid = count / 2;
    while (mid-- > 1) {
        head = head->next;
    }
    head->next = head->next->next;
    return temphead;
}
void printList(Node * ptr){
    while (ptr!= NULL) {
        cout << ptr->data << "->";
        ptr = ptr->next;
    }
    cout << "NULL"<<endl;
}
int main(){
    struct Node* head = createNode(2);
    head->next = createNode(4);
    head->next->next = createNode(6);
    head->next->next->next = createNode(8);
    head->next->next->next->next = createNode(10);
    cout << "Original linked list"<<endl;
    printList(head);
    head = deleteMiddle(head);
    cout<<endl;
    cout << "After deleting the middle of the linked list"<<endl;
    printList(head);
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

Original linked list
2->4->6->8->10->NULL

After deleting the middle of the linked list
2->4->8->10->NULL

まとめ

このアルゴリズムでは、まずリスト全体を走査してノード数をカウントし（O(n)）、その後に中央位置まで再度走査して削除を行います（O(n/2)）。したがって全体の計算量は O(n)、空間計算量は O(1) となります。

なお、より効率的な手法として、低速ポインタと高速ポインタ（2倍の速さで進むポインタ）を使う「Runner テクニック」を利用すれば、リストを事前にカウントすることなく一度の走査で中央ノードを特定できます。興味のある方はぜひ試してみてください。