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

本記事では、C++におけるリンクリスト（連結リスト）の先頭からM個のノードを残し、その直後のN個のノードを削除するアルゴリズムについて解説します。

リンクリストの定義

まず、データ（data）と次のノードへのポインタ（next）を持つリンクリストの構造体を定義します。

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

リスト生成用関数 createList

次に、Nodeへのダブルポインタとint型の値を受け取る createList(Node **headPtr, int new_data) 関数を作成します。関数内では、新しく作成したノードのnextポインタに現在のheadPtrを代入し、その後headPtrに新しいノードを設定することで、リストの先頭にノードを追加していきます。

void createList(Node ** headPtr, int new_data){
   Node* newNode = new Node();
   newNode->data = new_data;
   newNode->next = (*headPtr);
   (*headPtr) = newNode;
}

削除処理 deleteNnodesAfterM

deleteNnodesAfterM(Node *head, int M, int N) メソッドは、先頭ノードとM・Nの値を受け取ります。関数内では、Node* current にheadを代入し、作業用ポインタとして Node *t も宣言します。

void deleteNnodesAfterM(Node *head, int M, int N){
   Node *current = head, *t;
   int nodeCount;

関数の中核となるのは、currentがNULLを指すまで繰り返されるwhileループです。ループ内の最初のforループはM回繰り返され、終了時点でcurrentポインタは「M個目のノード」を指しています。その後、Node *t には current->next、つまり削除対象となる最初のノードが代入されます。

while (current){
   for (nodeCount = 1; nodeCount < M && current!= NULL; nodeCount++)
   current = current->next;
   if (current == NULL)
      return;
   t = current->next;

続く2番目のforループはN回繰り返され、tが指す位置から順にN個のノードをfree()で解放します。削除完了後、current->next にtを再接続してリンクを修復し、current をtへ進めることで、次の区間の処理へ移行します。

for (nodeCount = 1; nodeCount<=N && t!= NULL; nodeCount++){
   Node *temp = t;
   t = t->next;
   free(temp);
}
current->next = t;
current = t;

リスト表示用関数 printList

最後に、先頭ポインタを受け取ってリンクリスト全体を標準出力に表示する printList(Node *head) 関数です。

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

実装例

それでは、リンクリストのM個のノードの後にN個のノードを削除する完全な実装を見てみましょう。

#include <iostream>
using namespace std;
struct Node{
   int data;
   Node *next;
};
void createList(Node ** headPtr, int new_data){
   Node* newNode = new Node();
   newNode->data = new_data;
   newNode->next = (*headPtr);
   (*headPtr) = newNode;
}
void printList(Node *head){
   Node *temp = head;
   while (temp != NULL){
      cout<<temp->data<<" ";
      temp = temp->next;
   }
   cout<<endl;
}
void deleteNnodesAfterM(Node *head, int M, int N){
   Node *current = head, *t;
   int nodeCount;
   while (current){
      for (nodeCount = 1; nodeCount < M && current!= NULL; nodeCount++)
      current = current->next;
      if (current == NULL)
      return;
      t = current->next;
      for (nodeCount = 1; nodeCount<=N && t!= NULL; nodeCount++){
         Node *temp = t;
         t = t->next;
         free(temp);
      }
      current->next = t;
      current = t;
   }
}
int main(){
   Node* head = NULL;
   int M=2, N=2;
   createList(&head, 2);
   createList(&head, 4);
   createList(&head, 6);
   createList(&head, 8);
   createList(&head, 10);
   createList(&head, 12);
   createList(&head, 14);
   cout << "M = " << M<< " N = " << N<<endl;
   cout<< "Original linked list :"<<endl;
   printList(head);
   deleteNnodesAfterM(head, M, N);
   cout<<"Linked list after deletion :"<<endl;
   printList(head);
   return 0;
}

実行結果

上記のコードを実行すると、以下のような出力が得られます。M=2、N=2の場合、「2個残して2個削除」をリスト末尾まで繰り返していることが確認できます。

M = 2 N = 2

Original linked list :
14 12 10 8 6 4 2

Linked list after deletion :
14 12 6 4