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) 返回列表的新头。
输出:
时间复杂度: 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) 返回列表的新头。
输出:
给定链接列表 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)