极客教程C++程序 单链表中交替K节点翻转
给定一个链表，请写一个函数来高效地翻转每个交替的K（K是函数的输入值）个节点。请给出您的算法的复杂度。
示例：
输入：1->2->3->4->5->6->7->8->9->NULL 和 k = 3
输出：3->2->1->4->5->6->9->8->7->NULL。
方法1（处理前2k个节点，然后递归调用剩下的列表）：
这种方法实际上是在此文章中讨论的方法的扩展。
kAltReverse(struct node *head, int k)
1) 反转前k个节点。
2) 在修改后的列表中，头指向第k个节点。因此，将头的下一个改为第（k+1）个节点。
3) 移动当前指针以跳过接下来的k个节点。
4) 递归调用kAltReverse()来处理其余的n – 2k个节点。
5) 返回列表的新头。
// C++ program to reverse alternate
// k nodes in a linked list
#include <bits/stdc++.h>
using namespace std;
// Link list node
class Node
{
public:
int data;
Node* next;
};
/* Reverses alternate k nodes and
returns the pointer to the new
head node */
Node *kAltReverse(Node *head, int k)
{
Node* current = head;
Node* next;
Node* prev = NULL;
int count = 0;
/* 1) reverse first k nodes of the
linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
/* 2) Now head points to the kth node.
So change next of head to (k+1)th node*/
if(head != NULL)
head->next = current;
/* 3) We do not want to reverse next k
nodes. So move the current
pointer to skip next k nodes */
count = 0;
while(count < k-1 &&
current != NULL )
{
current = current->next;
count++;
}
/* 4) Recursively call for the list
starting from current->next. And make
rest of the list as next of first node */
if(current != NULL)
current->next = kAltReverse(current->next, k);
/* 5) prev is new head of the input list */
return prev;
}
// UTILITY FUNCTIONS
// Function to push a node
void push(Node** head_ref,
int new_data)
{
// Allocate node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
// Link the old list of the
// new node
new_node->next = (*head_ref);
// Move the head to point to the
// new node
(*head_ref) = new_node;
}
// Function to print linked list
void printList(Node *node)
{
int count = 0;
while(node != NULL)
{
cout<<node->data<<" ";
node = node->next;
count++;
}
}
// Driver code
int main(void)
{
// Start with the empty list
Node* head = NULL;
int i;
// Create a list
// 1->2->3->4->5...... ->20
for(i = 20; i > 0; i--)
push(&head, i);
cout << "Given linked list ";
printList(head);
head = kAltReverse(head, 3);
cout << "Modified Linked list ";
printList(head);
return(0);
}
// This code is contributed by rathbhupendra```
输出：
给定链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
修改后的链表
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
时间复杂度： O(n)
辅助空间： O(1)
方法2（处理k个节点并递归调用列表的其余部分）：
方法1将前k个节点反转，然后将指针移到k个节点之后。因此，方法1使用两个 while 循环，在一个递归调用中处理2k个节点。
此方法每次递归调用只处理k个节点。它使用第三个 bool 参数 b，该参数决定是否反转k个元素或仅移动指针。
_kAltReverse(struct node *head, int k, bool b)
1) 如果 b 为 true，则反转前 k 个节点。
2) 如果 b 是 false，则将指针向前移动 k 个节点。
3) 对 n-k 节点的其余部分递归调用 kAltReverse()，并将修改后的列表的其余部分连接到前 k 个节点的末尾。
4) 返回列表的新头。
// C++ 程序实现
// 上述方法
#include <bits/stdc++.h>
using namespace std;
// 链表节点
class node
{
public:
int data;
node* next;
};
// kAltReverse() 的辅助函数
node * _kAltReverse(node *node,
int k, bool b);
// 改用组大小为k的传统方法翻转链表。
node *kAltReverse(node *head, int k)
{
return _kAltReverse(head, k, true);
}
/* kAltReverse() 的辅助函数。
如果传入第三个参数 b 为 true，则仅翻转列表的 k 个节点，
否则将指针向前移动 k 个节点，并调用自身进行递归。*/
node * _kAltReverse(node *Node, int k, bool b)
{
if(Node == NULL)
return NULL;
int count = 1;
node *prev = NULL;
node *current = Node;
node *next;
/* 该循环有两个作用
1) 如果 b 为 true，则翻转 k 个节点
2) 如果 b 是 false，则移动当前指针 */
while(current != NULL && count <= k)
{
next = current->next;
// 只有在 b 为 true 时才反转节点
if(b == true)
current->next = prev;
prev = current;
current = next;
count++;
}
/* 3) 如果 b 为 true，则该节点是第 k 个节点。
因此，将剩余的列表附加到该节点后。
4) 附加后，返回新的头节点*/
if(b == true)
{
Node->next = _kAltReverse(current, k, !b);
return prev;
}
/* 如果 b 不为 true，则将
剩余的列表附加到 prev 后。
因此，将剩余的列表附加到 prev后*/
else
{
prev->next =
_kAltReverse(current, k, !b);
return Node;
}
}
// 实用函数
// 将节点推入链表
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)
{
int count = 0;
while(node != NULL)
{
cout << node->data << " ";
node = node->next;
count++;
}
}
// 主函数
int main(void)
{
// 从空列表开始
node* head = NULL;
int i;
// 创建列表
// 1->2->3->4->5...... ->20
for(i = 20; i > 0; i--)
push(&head;, i);
cout << "给定的链表 ";
printList(head);
head = kAltReverse(head, 3);
cout << "修改后的链表 ";
printList(head);
return(0);
}
// 本代码由 rathbhupendra 提供。```
输出：
给定链接列表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 修改后的链接列表 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
时间复杂度： O(n)
辅助空间 ：由于使用递归，调用堆栈的辅助空间为O(n)