数据结构单链表之以给定大小的组反转链表 | 第十二套
给定一个链表，编写一个函数来反转每 k 个节点（其中 k 是函数的输入）。
例子：
输入：1->2->3->4->5->6->7->8->NULL，K = 3
输出：3->2->1->6->5->4- >8->7->NULL
输入：1->2->3->4->5->6->7->8->NULL，K = 5
输出：5->4->3-> 2->1->8->7->6->NULL
算法：反向 （头，k）
反转大小为 k 的第一个子列表。倒车时跟踪下一个节点和上一个节点。让指向下一个节点的指针为next，指向前一个节点的指针为prev。请参阅此帖子以反转链接列表。
head->next = reverse(next, k) （递归调用列表的其余部分并链接两个子列表）
返回prev（prev成为列表的新头（参见这篇文章的迭代方法图）
下面是上述方法的实现：
#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* current = head; Node* next = NULL; Node* prev = NULL; int count = 0; while (current != NULL && count < k) { next = current->next; current->next = prev; prev = current; current = 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; } } int main() { Node* head = NULL; push(&head, 9); 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 << "Given linked list \n"; printList(head); head = reverse(head, 3); cout << "\nReversed Linked list \n"; printList(head); return (0); } 复制代码输出：
Given Linked List 1 2 3 4 5 6 7 8 9 Reversed list 3 2 1 6 5 4 9 8 7 复制代码
复杂度分析：
时间复杂度： O(n)。
列表的遍历只完成一次，它有 'n' 个元素。辅助空间： O(n/k)。
对于每个大小为 n 的链表，将在递归期间进行 n/k 或 (n/k)+1 调用。
作者：海拥
链接：https://juejin.cn/post/7015415373272989710