k个一组翻转链表

### Python 实现 K 个节点一组翻转链表 以下是基于题目描述和参考资料的 Python 实现方法。该算法满足以下条件： - 反转每 k 个节点的一组。 - 如果剩余节点不足 k 个，则保持原样。 - 算法仅使用 O(1) 的额外空间。 #### 定义链表结构 首先定义单链表的节点类 `ListNode`，这是实现的基础数据结构[^2]。 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next ``` --- #### 主函数逻辑 主函数负责整体流程控制，包括分组、反转以及连接各部分链表。 ```python def reverseKGroup(head: ListNode, k: int) -> ListNode: dummy = ListNode(0) # 创建哑节点以便于后续操作 dummy.next = head prev_group_end = dummy # 当前已处理部分的最后一节点 while True: a = prev_group_end.next # 获取当前组的第一个节点 if not has_k_nodes(a, k): # 判断是否有足够的 k 个节点 break b = get_kth_node(a, k) # 找到第 k+1 个节点 (即下一组的起点) new_a = reverse_list(a, b) # 对 [a, b) 节点范围内的子链表进行反转 # 连接已经完成的部分与新反转的部分 prev_group_end.next = new_a prev_group_end = a # 更新 prev_group_end 为本组最后一个节点（原始的 a） return dummy.next def has_k_nodes(node: ListNode, k: int) -> bool: """判断从给定节点开始是否存在至少 k 个节点""" current = node count = 0 while current and count < k: current = current.next count += 1 return count == k def get_kth_node(start: ListNode, k: int) -> ListNode: """获取从 start 开始的第 k+1 个节点""" current = start for _ in range(k): if not current: break current = current.next return current def reverse_list(start: ListNode, end: ListNode) -> ListNode: """反转从 start 到 end 前一个节点之间的链表""" prev, curr = None, start while curr != end: temp_next = curr.next curr.next = prev prev = curr curr = temp_next return prev ``` --- #### 测试代码 为了验证上述实现的有效性，可以编写测试用例来观察结果。 ```python # 辅助函数：创建链表 def create_linked_list(values): dummy = ListNode() current = dummy for value in values: current.next = ListNode(value) current = current.next return dummy.next # 辅助函数：打印链表 def print_linked_list(head): result = [] while head: result.append(str(head.val)) head = head.next print("->".join(result)) # 测试用例 if __name__ == "__main__": test_values = [1, 2, 3, 4, 5] k = 2 head = create_linked_list(test_values) reversed_head = reverseKGroup(head, k) print_linked_list(reversed_head) # 输出应为 2->1->4->3->5 ``` --- ### 解决方案说明 以上代码实现了按每 k 个节点一组翻转链表的功能，并遵循了以下原则： - **O(1) 额外空间**：除了几个指针变量之外未使用其他存储资源[^1]。 - **边界情况处理**：当剩余节点少于 k 时不会执行任何反转操作。 - **哑节点优化**：引入哑节点简化了头结点可能变动的情况下的复杂度[^3]。 ---