Home > Backend Development > C++ > body text

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

王林
Release: 2023-09-04 09:49:06
forward
1158 people have browsed it

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
Copy after login

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

Copy after login

Output

Original List : 1 2 3 4 5
Modified List : 3 2 1 5 4
Copy after login

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!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!