反转单向链表中交替的 K 个节点

给定一个链表，编写一个函数，该函数有效地反转每隔 K 个节点（K 是函数的输入）。

示例

方法 1（处理 2K 个节点并递归调用剩余列表）

这种方法实际上是该帖子中描述的方法的扩展。

kAltReversed(struct node *head, int k) 是一个反转函数。

1. 反转前 K 个节点。
2. 更新后的列表的头节点现在指向第 K 个节点。因此，将头节点的下一个节点更新为第 (K+1) 个节点。
3. 将当前指针重新定位以跳过接下来的 K 个节点。
4. 递归调用 kAltReversed() 来处理剩余的 n - 2k 个节点。
5. 返回列表的新头节点。

C++ 程序

输出

Given linked list 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
Modified Linked list 
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

• 时间复杂度为 O(n)。
• 空间复杂度为 O(n)。

方法 2（处理 K 个节点并递归调用剩余列表）

方法 1 反转前 K 个节点，然后将指针向前移动 K 个节点。方法 1 使用两个 while 循环在一次递归调用中处理 2K 个节点。

在递归调用中，此技术仅处理 K 个节点。它使用第三个布尔参数 b 来确定 K 个项目是否应被反转或简单地移动。

_kAltReversed(struct node *head, int k, bool b)

1. 如果 b 为真，则反转前 K 个节点。
2. 如果 b 为假，则将指针向前移动 K 个节点。
3. 递归调用 kAltReversed() 来处理剩余的 n - k 个节点，并将更改后的列表的其余部分连接到前 K 个节点的末尾。
4. 返回列表的新头节点。

C 语言程序

C++ 程序

输出

Given linked list 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
Modified Linked list 
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

• 时间复杂度为 O(n)。
• 空间复杂度为 O(n)。