K 个一组翻转链表

题目描述
给你链表的头节点 head，每 k 个节点一组进行翻转，返回修改后的链表。

• k 是正整数，且小于或等于链表长度。
• 如果节点总数不是 k 的整数倍，请将最后剩余的节点保持原有顺序。
• 不能只是单纯改变节点内部的值，而是需要实际进行节点交换。

示例
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

解题思路

1. 问题分析

• 链表翻转的扩展：需要分段翻转，且剩余不足 k 的部分不翻转。
• 关键点：
  1. 如何确定每组 k 个节点？
  2. 如何连接翻转后的子链表？
  3. 如何处理边界情况（如 k=1 或链表长度小于 k）？

2. 核心步骤

1. 遍历链表，确认每组范围：
   • 用指针标记每组的头尾（start 和 end）。
   • 若剩余节点不足 k，直接返回。
2. 翻转当前组：
   • 记录 end.next 作为下一组的起点。
   • 翻转 start 到 end 的部分。
3. 连接已翻转部分与后续链表：
   • 将翻转后的子链表头尾正确连接。

3. 递归与迭代的选择

• 递归：代码简洁，但栈空间复杂度为 O(n/k)。
• 迭代：更优的空间复杂度 O(1)，适合本题。

详细步骤（迭代法）

步骤 1：定义辅助函数

• reverse(start, end)：翻转从 start 到 end 的闭区间链表，返回新链表的头尾（end 变为新头，start 变为新尾）。

步骤 2：主流程

1. 创建哑节点（dummy node），指向头节点，简化边界处理。
2. 初始化 prev = dummy，标记当前组的前驱节点。
3. 循环直到链表末尾：
   • 用 end = prev 开始，向后移动 k 次，找到当前组的末尾。
   • 如果 end 为空，说明剩余节点不足 k，直接退出。
   • 记录 nextGroup = end.next。
   • 切断当前组与后续链表的连接：end.next = null。
   • 翻转 prev.next 到 end 的部分，得到新头 newHead 和新尾 newTail。
   • 连接：prev.next = newHead，newTail.next = nextGroup。
   • 更新 prev = newTail，继续处理下一组。

步骤 3：返回结果

• 返回 dummy.next 作为新链表的头。

举例说明

以 head = [1,2,3,4,5], k = 2 为例：

1. 初始：dummy -> 1 -> 2 -> 3 -> 4 -> 5，prev = dummy。
2. 第一组：
   • end 移动到节点 2，nextGroup = 3。
   • 翻转 1->2 得到 2->1，新头为 2，新尾为 1。
   • 连接：dummy.next = 2，1.next = 3。
   • 更新 prev = 1。
3. 第二组：
   • end 从 1 移动 2 次到节点 4，nextGroup = 5。
   • 翻转 3->4 得到 4->3。
   • 连接：1.next = 4，3.next = 5。
   • 更新 prev = 3。
4. 第三组：剩余节点数 1 < 2，结束。
   结果：dummy.next = 2 -> 1 -> 4 -> 3 -> 5。

代码实现（关键部分）

def reverseKGroup(head, k):
    def reverse(start, end):
        # 翻转区间 [start, end]，返回新头和新尾
        prev, curr = None, start
        while prev != end:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return end, start  # 新头是end，新尾是start

    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while head:
        end = prev
        # 检查是否够k个节点
        for _ in range(k):
            end = end.next
            if not end:
                return dummy.next
        nextGroup = end.next
        # 翻转当前组
        newHead, newTail = reverse(prev.next, end)
        # 连接前后部分
        prev.next = newHead
        newTail.next = nextGroup
        # 更新prev和head
        prev = newTail
        head = nextGroup

    return dummy.next

复杂度分析

• 时间复杂度：O(n)，每个节点被访问两次（遍历和翻转）。
• 空间复杂度：O(1)，仅使用常数额外空间。

总结

• 核心技巧：分组翻转 + 边界处理。
• 哑节点简化头节点变化的处理。
• 注意断开和连接链表的顺序，避免成环。