In diesem Problem erhalten wir einen Zeiger auf den Kopf der verknüpften Liste und eine Ganzzahl k. In einer Gruppe der Größe k müssen wir die verknüpfte Liste umkehren. Zum Beispiel -
Input : 1 <-> 2 <-> 3 <-> 4 <-> 5 (doubly linked list), k = 3 Output : 3 <-> 2 <-> 1 <-> 5 <-> 4
In diesem Problem werden wir einen rekursiven Algorithmus formulieren, um dieses Problem zu lösen. Bei dieser Methode verwenden wir die Rekursion und lösen das Problem mithilfe der Rekursion.
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
// push function to push a node into the list
Node* push(Node* head, int data) {
Node* new_node = new Node();
new_node->data = data;
new_node->next = NULL;
Node* TMP = head;
if (head == NULL) {
new_node->prev = NULL;
head = new_node;
return head;
}
while (TMP->next != NULL) { // going to the last node
TMP = TMP->next;
}
TMP->next = new_node;
new_node->prev = TMP;
return head; // return pointer to head
}
// function to print given list
void printDLL(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
Node* revK(Node* head, int k) {
if (!head)
return NULL;
head->prev = NULL;
Node *TMP, *CURRENT = head, *newHead;
int count = 0;
while (CURRENT != NULL && count < k) { // while our count is less than k we simply reverse the nodes.
newHead = CURRENT;
TMP = CURRENT->prev;
CURRENT->prev = CURRENT->next;
CURRENT->next = TMP;
CURRENT = CURRENT->prev;
count++;
}
if (count >= k) {
head->next = revK(CURRENT, k); // now when if the count is greater or equal
//to k we connect first head to next head
}
return newHead;
}
int main() {
Node* head;
for (int i = 1; i <= 5; i++) {
head = push(head, i);
}
cout << "Original List : ";
printDLL(head);
cout << "\nModified List : ";
int k = 3;
head = revK(head, k);
printDLL(head);
}
Original List : 1 2 3 4 5 Modified List : 3 2 1 5 4
Bei dieser Methode durchlaufen wir die Liste und iterieren, bis die Anzahl kleiner als k ist. Wir führen einen rekursiven Aufruf durch und geben den Wert an head -> next( Hier kehren wir die Liste beim Durchlaufen nur um, aber wenn k erreicht ist, müssen wir head auf das k-te Element einer anderen Liste verweisen lassen, zum Beispiel wenn unsere Liste 1 ist 2 3 4 5, unser k ist 3, wir haben das mittlere Element in 3 2 1 umgekehrt, aber jetzt brauchen wir 1, um auf 4 zu zeigen, weil dieses Element auch umgekehrt wird, deshalb verwenden wir den rekursiven Aufruf und machen zusätzliches if Aussagen).
In diesem Artikel haben wir die Lösung mithilfe von Rekursion gelöst. Wir haben auch ein C++-Programm für dieses Problem und unseren vollständigen Lösungsansatz kennengelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.
Das obige ist der detaillierte Inhalt vonKehren Sie die Gruppierung doppelt verknüpfter Listen nach gegebener Größe mit C++ um. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
