連結リストのK番目のノードをすべて削除する方法を解説

はじめに

この記事では、連結リスト（リンクリスト）のK番目のノードをすべて削除する方法を解説します。具体的には、kの倍数にあたる位置、つまりk番目、2k番目、3k番目……にあるノードを順番に削除していきます。

入力 : 112->231->31->41->54->63->71->85
    k = 3
出力 : 112->231->41->54->71->85
説明 : k = 3 のため、3番目のノードを削除します。
1回目の削除後 : 112->231->41->54->63->71->85
次に41から数えると、k番目にあたるノードは63です。
2回目の削除後、リストは次のようになります : 112->231->41->54->71->85
これ以降も同じ操作を繰り返します。

入力 : 14->21->23->54->56->61
    k = 1
出力 : 空のリスト
説明 : すべてのノードを削除する必要があります

この問題では、十分に効率的な標準的なアプローチを用いるため、さらなる最適化は必要ありません。

解決策のアプローチ

この問題では、カウンターを使いながら連結リストを走査します。カウンターがkに達したらそのノードを削除し、カウンターをリセットして、現在のノードから数えてk番目の位置にある次の要素を探します。

実装例（C++）

#include<bits/stdc++.h>
using namespace std;
/* 連結リストのノード */
struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** ref, int new_data) { // リストにデータを追加

   struct Node* new_n = new Node;
   new_n->data = new_data;
   new_n->next = (*ref);
   (*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // 削除関数

   if(prev == NULL) {
      prev = curr;
      curr = curr -> next;
      free(prev);
      prev = NULL;
   } else {
      prev -> next = curr -> next;
      auto tmp = curr;
      free(tmp); // メモリを解放
   }
}
/* 連結リストを表示する関数 */
void displayList(struct Node *head) {
   struct Node *temp = head;
   while (temp != NULL) {
      cout<<temp->data<<" ";
      temp = temp->next;
   }
}
// 新しいノードを作成する関数
struct Node *newNode(int x) {
   Node *temp = new Node;
   temp->data = x;
   temp->next = NULL;
   return temp;
}
int main() {
   struct Node* head = NULL;
   push(&head, 80);
   push(&head, 70);
   push(&head, 60);
   push(&head, 50);
   push(&head, 40);
   push(&head, 30);
   push(&head, 20);
   int k = 3; // 与えられたk
   Node* curr = head; // 現在のポインタ
   Node* prev = NULL; // 前のポインタ
   int count = 1; // 位置カウンター
   if(head == NULL || k == 0) // リストが空またはk = 0の場合
      cout << "Invalid\n";
   else {
      while(curr) { // リストを走査
         if(count == k) {
            deletek(prev, curr);
            curr = prev -> next;
            count = 1;
         } else {
            count++;
            prev = curr;
            curr = curr -> next;
         }
      }
      displayList(head); // 新しいリストを表示
   }
   return 0;
}

出力

20 30 50 60 80

このアプローチの計算量はO(N)です。ここでNは与えられた連結リストのサイズを表します。

コードの解説

上記のアプローチでは、まず3つの要素を管理します。1つ目は現在のノードを指すポインタ（current）、2つ目は直前のノードを指すポインタ（prev）、3つ目は位置を数えるカウンターです。カウンターがkと一致したタイミングで削除関数を呼び出し、prevとcurrentを引数として渡します。これにより現在のノードが削除され、メモリが解放されます。削除処理が完了したら、currentポインタを次の要素に移動し、カウンターを1にリセットします。この一連の処理を、currentがNULLになるまで繰り返します。

まとめ

この記事では、連結リストのK番目のノードをすべて削除する問題を解決しました。C++による実装例と、その解決に用いた標準的なアプローチについても学びました。同じプログラムは、C、Java、Pythonなど他のプログラミング言語でも記述することができます。この記事が皆さんのお役に立てば幸いです。