K个一组反转链表

题目描述
给定一个单链表的头节点 head 和一个整数 k，要求将链表每 k 个节点作为一组进行反转。如果链表中的节点总数不是 k 的整数倍，则最后剩余的节点保持原有顺序。例如，链表为 1→2→3→4→5，k=2 时，反转结果为 2→1→4→3→5；k=3 时，结果为 3→2→1→4→5。

解题思路
这个问题可以分解为两个关键步骤：

1. 判断剩余节点是否足够 k 个：若不足，直接返回当前部分。
2. 反转当前 k 个节点：通过指针操作将区间内的链表反转，并递归处理后续节点。

详细步骤

步骤 1：定义反转函数（反转区间 [a, b) 的节点）

• 目标：反转从节点 a 到节点 b（不含 b）的链表段，返回反转后的新头节点。
• 方法：使用迭代反转法，维护 pre、cur、nxt 三个指针。
  • 初始化：pre = null，cur = a。
  • 遍历直到 cur == b：
    • 保存 cur.next 到 nxt；
    • 将 cur.next 指向 pre；
    • pre 和 cur 分别向后移动：pre = cur，cur = nxt。
  • 返回 pre（即反转后的头节点）。

步骤 2：递归处理每 k 个分组

1. 检查从当前头节点开始的剩余节点是否足够 k 个：
   • 设置指针 p = head，遍历 k 次。若中途遇到 p == null，说明不足 k 个，直接返回 head（不反转）。
2. 反转当前 k 个节点：
   • 调用反转函数反转 [head, p) 区间，得到新头节点 newHead。
3. 递归处理后续链表：
   • 当前分组反转后，原头节点 head 变为分组的尾节点，将其 next 指向下一分组的反转结果（即递归调用 reverseKGroup(p, k)）。
4. 返回 newHead。

示例演示（链表 1→2→3→4→5，k=2）

1. 第一组：
   • 检查前 2 个节点（1→2），足够反转。
   • 反转后：2→1，原头节点 1 的 next 指向下一组结果。
2. 第二组：
   • 检查节点 3→4，足够反转。
   • 反转后：4→3，节点 3 的 next 指向剩余节点 5。
3. 最终结果：2→1→4→3→5。

边界情况处理

• 若 k=1，无需反转，直接返回原链表。
• 若链表为空或长度为 1，直接返回。

代码实现（参考）

def reverseKGroup(head, k):
    # 检查剩余节点是否足够 k 个
    p = head
    for _ in range(k):
        if not p:
            return head
        p = p.next
    
    # 反转当前 k 个节点
    new_head = reverse(head, p)
    # 递归处理后续分组，并连接
    head.next = reverseKGroup(p, k)
    return new_head

def reverse(a, b):
    pre, cur = None, a
    while cur != b:
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    return pre

关键点总结

• 反转区间 [a, b) 时，注意边界条件（b 不参与反转）。
• 递归前需确保剩余节点足够 k 个，否则直接返回。
• 时间复杂度为 O(n)，空间复杂度为 O(n/k)（递归栈深度）。