数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 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++ 程序以及我们解决此问题的完整方法（常规方法）。我们可以在其他语言（如 C、Java、Python 和其他语言）中编写相同的程序。我们希望您觉得本文有所帮助。
更新于: 2021年11月29日
209 次查看
广告