【C++】連結リストからxより大きいノードをすべて削除する方法

このチュートリアルでは、単方向連結リスト（Singly Linked List）から、指定した値 x より大きいデータを持つノードをすべて削除する方法 を解説します。

まずは、問題を解くための手順を確認しましょう。

解決の手順

1. データ（data）と次ノードへのポインタ（next）を持つ構造体を定義します。

2. 連結リストにノードを挿入する関数を作成します。

3. ダミーデータを使って連結リストを初期化します。

4. 連結リストを先頭から順に走査し、現在のノードのデータが x より大きいかどうかを判定します。

5. x より大きい場合は、そのノードを削除します。

ノード削除時に考慮すべき3つのケース

ノードを削除する関数では、以下の3つのケースを考慮する必要があります。

• 先頭ノードの場合： head ポインタを次のノードへ移動させます。

• 中間ノードの場合： 前のノードの next ポインタを、削除対象ノードの次のノードにつなぎ直します。

• 末尾ノードの場合： 前のノードの next ポインタを NULL にして、リンクを解除します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* getNewNode(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
void deleteGreaterNodes(Node** head_ref, int x) {
    Node *temp = *head_ref, *prev;
    if (temp != NULL && temp->data > x) {
        *head_ref = temp->next;
        free(temp);
        temp = *head_ref;
    }
    while (temp != NULL) {
        while (temp != NULL && temp->data <= x) {
            prev = temp;
            temp = temp->next;
        }
        if (temp == NULL) {
            return;
        }
        prev->next = temp->next;
        delete temp;
        temp = prev->next;
    }
}
void printLinkedList(Node* head) {
    while (head) {
        cout << head->data << " -> ";
        head = head->next;
    }
}
int main() {
    Node* head = getNewNode(1);
    head->next = getNewNode(2);
    head->next->next = getNewNode(3);
    head->next->next->next = getNewNode(4);
    head->next->next->next->next = getNewNode(5);
    head->next->next->next->next->next = getNewNode(6);
    int x = 3;
    cout << "Linked List before deletion:" << endl;
    printLinkedList(head);
    deleteGreaterNodes(&head, x);
    cout << "\nLinked List after deletion:" << endl;
    printLinkedList(head);
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

Linked List before deletion:
1 -> 2 -> 3 -> 4 -> 5 -> 6 ->
Linked List after deletion:
1 -> 2 -> 3 ->

この例では x = 3 としているため、4 以上の値を持つノード（4、5、6）が削除され、1 → 2 → 3 の連結リストだけが残ります。

処理のポイント

• 先頭ノードが条件に該当する場合でも正しく動作するよう、head へのポインタ（二重ポインタ）を使用しています。

• 内側の while ループで「x 以下のノード」をスキップし、該当ノードが見つかった時点で削除処理を行うことで、リスト全体を一度の走査で処理できます。

• 計算量は O(n)、必要な追加メモリは O(1) と効率的です。

まとめ

本記事では、C++ を使って単方向連結リストから x より大きい値を持つノードをすべて削除する方法を学びました。先頭・中間・末尾という位置ごとの削除処理の違いを理解することは、連結リスト操作の基礎として非常に重要です。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。