使用 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) { // 我们反转列表直到我们的计数小于 k
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
      count++;
   }
   if (next != NULL) // 如果我们的链接列表还没有结束，我们再次调用反向函数
      head->next = reverse(next, k);
   return prev;
}
void push(Node** head_ref, int new_data) { // 推送列表中数据的函数
   Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
void printList(Node* node) { // 打印链表的函数

   while (node != NULL) {
      cout << node->data << " ";
      node = node->next;
   }
   cout << "\n";
}
int main() {
   Node* head = NULL;

   int k = 3; // 给定的 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); // 这个函数将返回我们的新头
   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 和其他语言。我们希望这篇文章对您有所帮助。