Regroupement de listes chaînées inversées par taille donnée en utilisant C++

Dans cet article, nous traitons d'une liste chaînée unique et la tâche est d'inverser la liste en groupes de k. Par exemple -

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

Pour ce problème, une approche qui me vient à l'esprit consiste à suivre la liste et à inverser la liste lorsque la taille de la sous-liste atteint k et à continuer.

Méthode pour trouver la solution

Avec cette méthode, nous parcourons généralement la liste et gardons un compteur pour compter le nombre d'éléments dans la sous-liste. Lorsque le compteur atteint k, nous inversons cette partie.

Exemple

#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);
}

Sortie

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

La complexité temporelle de la méthode ci-dessus est O(N), où N est la taille de la liste donnée et la méthode est adaptée à la récursivité. Cette approche fonctionne également pour des contraintes plus élevées.

Explication du code ci-dessus

Dans cette méthode, nous allons parcourir le tableau et continuer à l'inverser jusqu'à ce que notre variable compteur soit inférieure à k. Lorsque le compteur atteint la valeur de k, on appelle une autre fonction d'inversion pour connecter le dernier nœud de cette sous-liste au premier nœud de la sous-liste inversée suivante. Cela se fait de manière récursive.

Conclusion

Dans cet article, nous avons résolu le problème de l'inversion d'une liste chaînée par groupes d'une taille donnée en utilisant la récursivité. Nous avons également appris un programme C++ pour résoudre ce problème et une méthode complète pour résoudre ce problème (Normal). Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que cet article vous a été utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!