Reverse linked list grouping by given size using C++

In this article, we deal with a singly linked list and the task is to reverse the list in groups of k. For example -

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

For this problem, one approach that comes to mind is to tail the list and reverse the list when the size of the sublist reaches k and continue.

Methods to find solutions

With this method, we usually iterate through the list and keep a counter to count the number of elements in the sublist. When the counter reaches a count of k, we invert that part.

Example

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

Output

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

The time complexity of the above method is O(N), where N is the size of the given list, and This method works recursively. This approach also works for higher constraints.

Explanation of the above code

In this method we will iterate through the array and keep reversing it until our counter variable is less than k. When the counter reaches the value of k, we call another inversion function to connect the last node of this sublist to the first node of the next inverted sublist. This is done recursively.

Conclusion

In this article, we solved the problem of reversing a linked list by groups of a given size using recursion. We also learned a C program to solve this problem and a complete method to solve this problem (Normal). 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 linked list grouping by given size using C++. For more information, please follow other related articles on the PHP Chinese website!