在本文中，我们处理一个单链表，任务是以 k 为一组反转该列表。例如 –
Input: 1->2->3->4->5->6->7->8->NULL, K = 3Output: 3->2->1->6->5->4->8->7->NULLInput: 1->2->3->4->5->6->7->8->NULL, K = 5Output: 5->4->3->2->1->8
对于这个问题，想到的一种方法是尾随列表并在子列表的大小达到 k 并继续时反转列表。
寻找解决方案的方法
通过这种方法，我们通常会遍历列表并保留一个计数器来计算子列表中的元素数量。当计数器达到 k 的计数时，我们反转该部分。
示例
#include 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 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 <data <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 list1 2 3 4 5 6 7 8New list3 2 1 6 5 4 8 7
上述方法的时间复杂度为O(N)，其中N是给定列表的大小，并且该方法适用于递归。这种方法也适用于更高的约束。
立即学习“C++免费学习笔记（深入）”；
上述代码的解释
我们将在这种方法中遍历数组并不断反转它，直到我们的计数器变量小于 k 。当计数器达到 k 的值时，我们调用另一个反转函数将该子列表的最后一个节点连接到下一个反转子列表的第一个节点。这是通过递归完成的。
结论
在本文中，我们解决了使用递归按给定大小的组反转链表的问题。我们还学习了解决此问题的 C++ 程序以及解决此问题的完整方法（Normal）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望这篇文章对您有所帮助。
以上就是使用C++按给定大小将链表分组反转的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445385.html
微信扫一扫 
支付宝扫一扫 
