主函数 reverseKGroup
目的:反转链表中的每 k 个节点。
参数:
head: 链表的头部。
k: 需要反转的节点数量。
返回值:反转后的链表头部。
检查是否有足够的节点进行反转:
初始化 node 指向 head。
循环 k 次,检查 node 是否为 nil。如果是,则说明剩余节点不足 k 个,直接返回原始的 head。
如果有足够的节点,继续执行后续步骤。
反转前 k 个节点:
调用 reverse 函数来反转从 head 到 node 的节点,并将结果赋值给 newHead。
连接反转后的部分与剩余链表:
将反转后的链表尾部连接到下一段待反转的链表上,即 = reverseKGroup(node, k)。
返回新的链表头部:
返回 newHead 作为新的链表头部。
辅助函数 reverse
目的:反转从 first 到 last (不包括 last)之间的链表。
参数:
first: 反转链表的起始节点。
last: 反转链表的终止节点。
返回值:反转后的链表头部。
初始化:
设置 prev 为 last。
反转链表:
循环直到 first 与 last 相遇。
保存 first 的下一个节点 tmp。
将 first 的 Next 指向 prev,完成反转。
移动 prev 和 first 指针。
返回新的头部:
返回 prev 作为反转后的链表头部。
时间与空间复杂度
时间复杂度: O(n),其中 n 是链表的长度。每个节点被访问两次(一次在 reverseKGroup 中检查是否有足够的节点,一次在 reverse 中进行反转)。
空间复杂度: O(log n)。递归调用栈的最大深度取决于链表的长度,最坏情况下为 O(n),但平均情况下为 O(log n)。