In diesem Artikel erklären wir, wie man jeden k-ten Knoten in einer verknüpften Liste löscht. Wir müssen jeden Knoten löschen, der sich auf einem Vielfachen von k befindet, d. h. wir müssen Knoten an den Positionen k, 2*k, 3*k usw. löschen.
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
In diesem Problem werden wir eine triviale Methode anwenden, die effizient genug ist, sodass wir sie nicht optimieren müssen.
In diesem Problem werden wir eine verknüpfte Liste mit einem Zähler durchlaufen. Wenn der Zähler k erreicht, löschen wir den Knoten und aktualisieren den Zähler, um das nächste Element an der k-ten Position des aktuellen Knotens zu finden.
#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
Die zeitliche Komplexität der obigen Methode beträgt O(N), wobei N die Größe der angegebenen verknüpften Liste ist.
In der obigen Methode behalten wir zunächst drei Dinge bei: Das erste ist der aktuelle Zeiger, das zweite ist der vorherige Zeiger und das dritte ist der Positionszähler. Wenn nun unser Positionszähler gleich k ist, löschen wir einen bestimmten Knoten, rufen die Löschfunktion auf und übergeben den vorherigen und aktuellen Zähler als Parameter. Dann löschen wir den aktuellen Knoten und geben den Platz frei. Wenn die Löschfunktion abgeschlossen ist, bewegen wir uns Setzen Sie den aktuellen Zeiger auf das nächste Element und aktualisieren Sie den Zähler auf 1, indem Sie diesen Block in einer Schleife durchlaufen, bis der aktuelle Zeiger NULL wird.
In diesem Artikel haben wir das Problem gelöst, jeden k-ten Knoten einer verknüpften Liste zu löschen. Wir haben auch ein C++-Programm und einen vollständigen (trivialen) Ansatz zur Lösung dieses Problems gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie finden diesen Artikel hilfreich.
Das obige ist der detaillierte Inhalt vonLöschen Sie jeden K-ten Knoten in der verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
