使用C++按给定大小将链表分组反转

在本文中，我们处理一个单链表，任务是以 k 为一组反转该列表。例如 -

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

对于这个问题，想到的一种方法是尾随列表并在子列表的大小达到 k 并继续时反转列表。

寻找解决方案的方法

通过这种方法，我们通常会遍历列表并保留一个计数器来计算子列表中的元素数量。当计数器达到 k 的计数时，我们反转该部分。

示例

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

输出

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

上述方法的时间复杂度为O(N)，其中N是给定列表的大小，并且该方法适用于递归。这种方法也适用于更高的约束。

上述代码的解释

我们将在这种方法中遍历数组并不断反转它，直到我们的计数器变量小于 k 。当计数器达到 k 的值时，我们调用另一个反转函数将该子列表的最后一个节点连接到下一个反转子列表的第一个节点。这是通过递归完成的。

结论

在本文中，我们解决了使用递归按给定大小的组反转链表的问题。我们还学习了解决此问题的 C++ 程序以及解决此问题的完整方法（Normal）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望这篇文章对您有所帮助。

以上是使用C++按给定大小将链表分组反转的详细内容。更多信息请关注PHP中文网其他相关文章！