Inverser le regroupement de listes doublement chaînées par taille donnée en utilisant C++

Dans ce problème, nous obtenons un pointeur vers la tête de la liste chaînée et un entier k. Dans un groupe de taille k, nous devons inverser la liste chaînée. Par exemple -

Input : 1 <-> 2 <-> 3 <-> 4 <-> 5 (doubly linked list), k = 3
Output : 3 <-> 2 <-> 1 <-> 5 <-> 4

Méthodes pour trouver une solution

Dans ce problème, nous formulerons un algorithme récursif pour résoudre ce problème. Dans cette méthode, nous utiliserons la récursivité et résoudrons le problème en utilisant la récursivité.

Exemple

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

Sortie

Original List : 1 2 3 4 5
Modified List : 3 2 1 5 4

Explication du code ci-dessus

Dans cette méthode, nous parcourons la liste et itérons jusqu'à ce que le nombre soit inférieur à k. Nous effectuons un appel récursif donnant la valeur à head -> next (Ici, nous inversons simplement la liste pendant le parcours, mais lorsque k est atteint, nous devons faire pointer head vers le kième élément d'une autre liste, par exemple si notre liste est 1 2 3 4 5, notre k est 3, nous avons inversé l'élément du milieu pour qu'il soit 3 2 1, mais maintenant nous avons besoin de 1 pour pointer vers 4 car cet élément sera également inversé, c'est pourquoi nous utilisons l'appel récursif et faisons des if supplémentaires déclarations).

Conclusion

Dans cet article, nous avons résolu en utilisant Recursion. Nous avons également appris un programme C++ pour ce problème et notre approche complète pour le résoudre. 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!