k个一组翻转链表
- 题目
- 题目描述
- 示例 1：
- 示例 2：
- 提示：
- 题目链接
- 题解
- 解题思路
- python实现
- 代码分析
- 提交结果
题目
题目描述
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
题目链接
k个一组翻转链表
题解
解题思路
我们需要保证：
- 正确地反转每 k 个节点的组。
- 如果剩余节点不足 k 个，则保持原样。
- 反转后的链表部分要正确连接起来。
- 算法只使用 O(1) 的额外空间。
python实现
下面是经过仔细检查后，重新整理的 Python 实现代码，用于解决 k 个一组反转链表的问题：
def reverseKGroup(head: ListNode, k: int) -> ListNode:# 创建一个哑节点，方便处理边界情况dummy = ListNode(0)dummy.next = headgroup_prev = dummywhile True:# 检查接下来是否有至少k个节点kth_node = group_prevfor _ in range(k):kth_node = kth_node.nextif not kth_node:return dummy.next# 记录下一组的起始位置group_next = kth_node.next# 反转当前组内的节点prev, curr = group_prev.next, group_prev.next.nextfor _ in range(k - 1):temp = curr.nextcurr.next = prevprev = currcurr = temp# 连接反转后的组与之前的节点和之后的节点first_node_of_group = group_prev.next # 原来的第一个节点（现在是最后一个）first_node_of_group.next = group_next # 将该组最后的节点指向下一组的第一个节点group_prev.next = kth_node # 将前一组的最后节点指向前一组反转后的第一个节点# 移动到下一组group_prev = first_node_of_groupreturn dummy.next
代码分析
这段代码的关键点在于：
- 使用哑节点
dummy来简化头结点的操作。 - 在进入反转逻辑之前，先检查接下来是否还有至少 k 个节点。
- 使用两个指针
prev和curr来进行局部反转操作，其中prev最终会成为反转后这一组的新头部。 - 通过保存每一组的第一个节点（反转后的最后一个节点），我们可以在完成反转后正确地连接链表的不同部分。
- 更新
group_prev到当前组反转后的最后一个节点，准备进入下一轮循环。
这个算法保证了对于任何有效的输入都能正确工作，并且它仅使用常数级别的额外空间来存储指针变量，符合 O(1) 空间复杂度的要求。
提交结果
