Umgekehrte Gruppierung verknüpfter Listen nach gegebener Größe mit C++

In diesem Artikel beschäftigen wir uns mit einer einfach verknüpften Liste und die Aufgabe besteht darin, die Liste in Gruppen von k umzukehren. Zum Beispiel -

Input: 1->2->3->4->5->6->7->8->NULL, K = 3
Output: 3->2->1->6->5->4->8->7->NULL

Input: 1->2->3->4->5->6->7->8->NULL, K = 5
Output: 5->4->3->2->1->8

Für dieses Problem fällt mir ein Ansatz ein, die Liste zu beenden und umzukehren, wenn die Größe der Unterliste k erreicht, und fortzufahren.

Methode zum Finden der Lösung

Mit dieser Methode durchlaufen wir normalerweise die Liste und führen einen Zähler, um die Anzahl der Elemente in der Unterliste zu zählen. Wenn der Zähler einen Zählerstand von k erreicht, invertieren wir diesen Teil.

Beispiel

#include <bits/stdc++.h>
using namespace std;
class Node {
   public:
   int data;
   Node* next;
};
Node* reverse(Node* head, int k) {
   if (!head)
      return NULL;
   Node* curr = head;
   Node* next = NULL;
   Node* prev = NULL;
   int count = 0;
   while (curr != NULL && count < k) { // we reverse the list till our count is less than k
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
      count++;
   }
   if (next != NULL) // if our link list has not ended we call reverse function again
      head->next = reverse(next, k);
   return prev;
}
void push(Node** head_ref, int new_data) { // function for pushing data in the list
   Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
void printList(Node* node) { // function to print linked list

   while (node != NULL) {
      cout << node->data << " ";
      node = node->next;
   }
   cout << "\n";
}
int main() {
   Node* head = NULL;

   int k = 3; // the given k

   push(&head, 8);
   push(&head, 7);
   push(&head, 6);
   push(&head, 5);
   push(&head, 4);
   push(&head, 3);
   push(&head, 2);
   push(&head, 1);

   cout << "Original list \n";
   printList(head);

   head = reverse(head, k); // this function will return us our new head
   cout << "New list \n";
   printList(head);
   return (0);
}

Ausgabe

Original list
1 2 3 4 5 6 7 8
New list
3 2 1 6 5 4 8 7

Die zeitliche Komplexität der obigen Methode beträgt O(N), wobei N die Größe der gegebenen Liste ist und die Methode für die Rekursion geeignet ist. Dieser Ansatz funktioniert auch für höhere Einschränkungen.

Erklärung des obigen Codes

Bei dieser Methode durchlaufen wir das Array und kehren es so lange um, bis unsere Zählervariable kleiner als k ist. Wenn der Zähler den Wert von k erreicht, rufen wir eine weitere Inversionsfunktion auf, um den letzten Knoten dieser Unterliste mit dem ersten Knoten der nächsten invertierten Unterliste zu verbinden. Dies geschieht rekursiv.

Fazit

In diesem Artikel haben wir das Problem der Umkehrung einer verknüpften Liste nach Gruppen einer bestimmten Größe mithilfe der Rekursion gelöst. Wir haben auch ein C++-Programm zur Lösung dieses Problems und eine vollständige Methode zur Lösung dieses Problems (Normal) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

Das obige ist der detaillierte Inhalt vonUmgekehrte Gruppierung verknüpfter Listen nach gegebener Größe mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!