Reverse doubly linked list grouping by given size using C++

In this problem, we get a pointer to the head of the linked list and an integer k. In a group of size k, we need to reverse the linked list. For example -

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

Methods to find solution

In this problem we will formulate a recursive algorithm to solve this problem. In this method we will use recursion and solve the problem using recursion.

Example

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

Output

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

Explanation of the above code

In this method, we loop through the list and iterate until the count is less than k. We make a recursive call giving the value to head -> next( Here we are just reversing the list while traversing, but when k is reached we need to make head point to the kth element of another list, for example if our list is 1 2 3 4 5, our k is 3, we reversed the middle element to be 3 2 1, but now we need 1 to point to 4 because that element will also be reversed, so that's why we use the recursive call and make additional if statements.).

Conclusion

In this article, we solved the problem using recursion. We also learned a C program for this problem and our complete approach to solving it. We can write the same program in other languages ​​such as C, java, python and other languages. We hope this article was helpful to you.

The above is the detailed content of Reverse doubly linked list grouping by given size using C++. For more information, please follow other related articles on the PHP Chinese website!