K 个一组翻转链表

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

• k 是正整数，且小于或等于链表长度。
• 如果节点总数不是 k 的整数倍，请将最后剩余的节点保持原有顺序。

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

第一步：理解问题核心

1. 分段处理：链表需按 k 个节点为一组进行翻转，类似“局部翻转 + 拼接”。
2. 边界处理：
   • 若剩余节点数不足 k，则不翻转。
   • 需正确处理组与组之间的连接。

第二步：设计子函数：翻转一段链表

翻转区间 [head, tail) 内的节点（左闭右开，即不包含 tail），返回新链表的头尾节点。

def reverse(head, tail):
    prev = tail  # 关键：翻转后的头节点应接上下一组的头
    curr = head
    while curr != tail:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev, head  # 新头为prev，新尾为原head

第三步：主逻辑流程

1. 遍历链表，用指针 start 标记当前组的起始节点。
2. 检查剩余长度：从 start 开始向后数 k 次，若遇到末尾则直接返回。
3. 记录下一组头节点：end_next = end.next（end 为当前组第 k 个节点）。
4. 翻转当前组：调用 reverse(start, end.next)，得到新头 new_head 和新尾 new_tail。
5. 连接前一组与当前组：若当前组不是第一组，将前一组的尾节点指向 new_head。
6. 更新指针：将 start 设为 end_next，继续处理下一组。

第四步：具体步骤演示（示例：k=2）

初始链表：1→2→3→4→5

1. 第一组 [1,2]：
   • 翻转后为 2→1，新头=2，新尾=1。
   • 整体链表变为 2→1→3→4→5。
2. 第二组 [3,4]：
   • 翻转后为 4→3，新头=4，新尾=3。
   • 将前一组的尾（节点1）指向4：2→1→4→3→5。
3. 剩余 [5] 不足 k，保持不动。
   结果：2→1→4→3→5

第五步：代码实现（Python）

def reverseKGroup(head, k):
    dummy = ListNode(0)
    dummy.next = head
    prev_end = dummy  # 前一组的尾节点
    
    while head:
        # 检查是否够k个节点
        tail = prev_end
        for _ in range(k):
            tail = tail.next
            if not tail:
                return dummy.next
        
        # 记录下一组头节点
        next_head = tail.next
        
        # 翻转当前组
        new_head, new_tail = reverse(head, tail.next)
        
        # 连接前一组与当前组
        prev_end.next = new_head
        new_tail.next = next_head
        
        # 更新指针
        prev_end = new_tail
        head = next_head
    
    return dummy.next

第六步：复杂度分析

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

关键点总结

• 使用哑节点（dummy）简化头节点处理。
• 翻转时采用“左闭右开”区间，便于连接下一组。
• 每次翻转前需检查剩余节点是否够 k 个。