リンクされたリスト内の K 番目のノードごとに削除します

この記事では、リンク リスト内の k 番目のノードごとに削除する方法を説明します。 k の倍数にあるすべてのノードを削除する必要があります。つまり、位置 k、2*k、3*k などにあるノードを削除する必要があります。

Input : 112->231->31->41->54->63->71->85
   k = 3
Output : 112->231->41->54->71->85
Explanation: As 3 is the k-th node after its deletion list would be :
First iteration :112->231->41->54->63->71->85
Now we count from 41 the next kth node is 63
After the second iteration our list will become : 112->231->41->54->71->85
And our iteration continues like this.

Input: 14->21->23->54->56->61
   k = 1
Output: Empty list
Explanation: All nodes need to be deleted

この問題では、十分に効率的な一般的な方法を適用するため、最適化する必要はありません。

解決策を見つける方法

この問題では、カウンターを使用してリンク リストをたどります。カウンタが k に達すると、ノードを削除し、カウンタを更新して、現在のノードの k 番目の位置にある次の要素を見つけます。

例

#include<bits/stdc++.h>
using namespace std;
/* Linked list Node */
struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the data into the list

   struct Node* new_n = new Node;
   new_n->data = new_data;
   new_n->next = (*ref);
   (*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // delete function

   if(prev == NULL) {
      prev = curr;
      curr = curr -> next;
      free(prev);
      prev = NULL;
   } else {
      prev -> next = curr -> next;
      auto tmp = curr;
      free(tmp); // freeing the space
   }
}
/* Function to print linked list */
void displayList(struct Node *head) {
   struct Node *temp = head;
   while (temp != NULL) {
      cout<<temp->data<<" ";
      temp = temp->next;
   }
}
// Function to create a new node.
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; // given k
   Node* curr = head; // current pointer
   Node* prev = NULL; // previous pointer
   int count = 1; // position counter
   if(head == NULL || k == 0) // if list is already empty or k = 0
      cout << "Invalid\n";
   else {
      while(curr) { // traversing the list
         if(count == k) {
            deletek(prev, curr);
            curr = prev -> next;
            count = 1;
         } else {
            count++;
            prev = curr;
            curr = curr -> next;
         }
      }
      displayList(head); // printing the new list
   }
   return 0;
}

出力

20 30 50 60 80

上記のメソッドの時間計算量は O(N) です。ここで、N は指定されたリンクのサイズですリスト。

上記コードの説明

上記のメソッドでは、まず 3 つのものを保持します。1 つ目は現在のポインタ、2 つ目は前のポインタ、3 つ目は位置カウンタです。位置カウンタが k に等しい場合、特定のノードを削除し、delete 関数を呼び出し、以前と現在のカウンタをパラメータとして渡します。次に、現在のノードを削除してスペースを解放し、削除関数が完了したら、移動します。次の要素への現在のポインタを更新し、カウンタを 1 に更新して、現在のポインタが NULL になるまでこのブロックをループします。

結論

この記事では、リンク リストの k 番目のノードごとに削除するという問題を解決しました。また、C プログラムと、この問題を解決するための完全な (簡単な) 方法も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がリンクされたリスト内の K 番目のノードごとに削除しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。