C++で連結リストのM個のノードの後にN個のノードを削除する方法

このチュートリアルでは、C++を使って連結リスト（リンクドリスト）の中から、M個のノードをスキップした直後にあるN個のノードを削除する方法を解説します。

アルゴリズムの手順

まず、問題を解決するための全体の流れを確認しましょう。

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

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

• M個のノードの後にN個のノードを削除する関数を実装します。

  • 作業用ポインタをヘッドポインタで初期化します。

  • 連結リストの末尾に達するまで反復処理を行います。

  • M個のノード分だけポインタを前進させます。

  • 続くN個のノードを削除します。

  • ポインタを次のノードへ移動して処理を繰り返します。

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

サンプルコード

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

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *next;
};
void insertNode(Node ** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    *head_ref = new_node;
}
void printLinkedList(Node *head) {
    Node *temp = head;
    while (temp != NULL) {
        cout<< temp->data << " -> ";
        temp = temp->next;
    }
    cout << "Null" << endl;
}
void deleteNNodesAfterMNodes(Node *head, int M, int N) {
    Node *current = head, *temp;
    int count;
    while (current) {
        // M個のノードをスキップ
        for (count = 1; count < M && current!= NULL; count++) {
            current = current->next;
        }
        // 連結リストの末尾に到達した場合
        if (current == NULL) {
            return;
        }
        // M個のノードの後に続くN個のノードを削除
        temp = current->next;
        for (count = 1; count <= N && temp != NULL; count++) {
            Node *deletingNode = temp;
            temp = temp->next;
            free(deletingNode);
        }
        current->next = temp;
        current = temp;
    }
}
int main() {
    Node* head = NULL;
    int M = 1, N = 2;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    insertNode(&head, 6);
    insertNode(&head, 7);
    insertNode(&head, 8);
    insertNode(&head, 9);
    cout << "Linked list before deletion: ";
    printLinkedList(head);
    deleteNNodesAfterMNodes(head, M, N);
    cout << "Linked list after deletion: ";
    printLinkedList(head);
    return 0;
}

実行結果

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

Linked list before deletion: 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> Null
Linked list after deletion: 9 -> 6 -> 3 -> Null

コードのポイント

このアルゴリズムでは、M = 1 の場合は各ノードを1つ残し、その後に続く N = 2 個のノードが削除されるため、元のリスト「9 → 8 → 7 → 6 → 5 → 4 → 3 → 2 → 1」が「9 → 6 → 3」となります。

重要なのは、ノードを削除する際に free() を呼び出してメモリを適切に解放している点です。これによりメモリリークを防ぐことができます。また、リストの途中で末尾に到達した場合にも安全に対処できるよう、NULLチェックを各段階で行っています。

計算量はリストの長さを L とすると O(L) となり、各ノードを一度だけ走査する効率的なアルゴリズムです。

まとめ

本チュートリアルでは、連結リスト内のM個のノードの後に続くN個のノードを削除する方法を学びました。ポインタ操作とメモリ管理の基本的なテクニックが詰まった良い練習問題なので、ぜひ自分でもMやNの値を変えて動作を試してみてください。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。