25. K 个一组翻转链表

题目链接：25. K 个一组翻转链表

题目描述

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

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

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

核心思考：分组截断与局部反转

这是一道极具代表性的链表综合操作题。它的核心难点不在于“如何反转链表”，而在于如何优雅地将一条长链表按 k 的步长进行分组、切断、分别反转，最后再分毫无差地重新缝合起来。

为了条理清晰，我们可以将整个过程抽象为几个高度模块化的步骤循环执行：

1. 哑节点 (Dummy Node) 基址

像绝大多数可能导致原始头节点（head）发生变更的链表题一样，我们必须在最前方安插一个 dummy 节点作为不动的锚点，从而避免首个 k 区间反转时的特殊边界判断代码。

2. 探路与切断 (分组探测)

我们需要一个 tail 指针每次向后探测 k 步，来界定当前这一组需要反转的区间（从 start 到 tail）。

• 如果在走完 k 步之前 tail 就变为空了，说明剩余节点不足 k 个，按照题意直接跳出循环，任务结束。
• 如果成功走完 k 步，为了让这段待反转的子链表成为一个独立的“标准链表”，我们需要将其尾部与大部队暂时切断（tail.next = None）。当然，在切断前务必用 next_group 暂存好下一组的起点，以免链表在这断档。

3. 局部反转与复位缝合

我们将切取下来的、以 start 为首的独立子链表，交接给标准的反转工具函数 reverse() 处理。
反转归来后，原本的头部 start 成为了这组的尾部，而反转函数返回的 new_head 则是这组的新头部。最后，我们将反转后的小链表两头重新缝合回整体大链表之中：

• 让上一组的尾巴（pre）接上当前组的新头（new_head）。
• 让当前组的新尾巴（原本的 start）接上后方断开的余下链表（next_group）。

至此，一个 k 区间的反转完美竣工。只需推进指针，即可进入下一轮相同的剥离、反转与缝合。

解题思路 (Python)

我们可以将反转操作单独提炼为一个子函数 reverse()，专门负责一条以 None 结尾的单链表的标准反转任务。

class Solution:
    # 复用
    def reverse(self, head: ListNode) -> ListNode:
        prev, curr = None, head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev, curr = curr, nxt
        return prev

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        
        while head:
            tail = pre
            # 向后走 k 步定位 end
            for i in range(k):
                tail = tail.next
                if not tail:
                    return dummy.next # 剩余不足 k 个，按题目要求保持原样
            
            # 切断
            next_group = tail.next
            tail.next = None # 断开与后方的连接
            
            # 反转并重新缝合
            start = pre.next
            # 调用 reverse 反转这一段，并更新 pre.next 和 start.next
            new_head = self.reverse(start)
            pre.next = new_head
            start.next = next_group

            # 指针位移，准备处理下一组
            pre = start
            head = next_group
            
        return dummy.next

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是链表节点总数。每个节点都会被探路指针 tail 遍历一次，绝大部分节点还会被 reverse() 内部再遍历反转一次。平摊下来每组操作的常数极小，整体开销严格把控在线性级别 $O(N)$。
• 空间复杂度：$O(1)$。算法依然坚持原地指针变换运作，除了静态的几个循环追踪指针以及辅助切断用的几个锚点变量，无论是探路还是反转工具函数都不涉及随链表规模同步扩张的额外堆栈内存损耗。