题目描述给你链表的头节点head每k个节点一组进行翻转请你返回修改后的链表。k是一个正整数它的值小于或等于链表的长度。如果节点总数不是k的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。示例示例 1输入head [1,2,3,4,5],k 2输出[2,1,4,3,5]示例 2输入head [1,2,3,4,5],k 3输出[3,2,1,4,5]提示链表中的节点数目为n1 k n 50000 Node.val 1000进阶你可以设计一个只用O(1)额外内存空间的算法解决此问题吗解题思路核心思想本题要求我们每 k 个节点一组进行翻转并且如果最后一组不足 k 个则不翻转。这类似于单链表的局部反转但需要将每一组翻转后与前后部分正确连接。关键点分组需要知道每一组的起点和终点以及前后连接的节点。翻转对每组内的节点进行反转注意翻转后头变尾尾变头。连接将翻转后的子链表重新接回原链表。方法迭代 哨兵节点为了统一处理头节点可能被翻转的情况我们引入一个虚拟头节点dummy node指向真正的头节点。这样无论头节点怎么变我们都能通过dummy.next得到新头。步骤分解定义哨兵节点dummy ListNode(0, head)并设置两个指针pre和end。pre指向每次要翻转的一组链表的前一个节点初始为dummyend指向每次要翻转的一组链表的最后一个节点。循环分组每次让end从pre开始向后移动 k 步如果移动过程中end变为None说明剩余节点不足 k 个则直接返回dummy.next。记录下一组的起点next_group end.next因为翻转后end会成为这一组的头而原来的头会变成尾需要连接下一组。断开当前组将end.next设为None这样当前组就独立出来了。翻转当前组定义start pre.next然后对从start到end的链表进行翻转。翻转函数可以采用经典的迭代法返回新的头即原来的end和新的尾即原来的start。连接前后pre.next指向翻转后的新头即end而翻转后的新尾start的next指向next_group。更新 pre将pre移动到新的尾即start然后继续下一轮循环。翻转子链表函数实现一个辅助函数reverseList(head)给定一个链表的头节点返回翻转后的新头。我们可以用迭代法defreverseList(head):prevNonecurrheadwhilecurr:next_tempcurr.nextcurr.nextprev prevcurr currnext_tempreturnprev# 新的头注意这个函数会改变原链表并且返回的新头是原来的尾节点。图解示例以head [1,2,3,4,5],k 2为例初始状态dummy - 1 - 2 - 3 - 4 - 5 - null pre dummy第一组end从pre走 2 步到达节点 2。start pre.next 1next_group 3。dummy - 1 - 2 - null (断开后) 3 - 4 - 5 - null翻转1-2得到2-1。然后连接dummy - 2 - 1 - 3 - 4 - 5 - nullpre更新为新的尾1。第二组end从pre走 2 步到达节点 4。start 3next_group 5。dummy - 2 - 1 - 3 - 4 - null 5 - null翻转3-4得到4-3。连接dummy - 2 - 1 - 4 - 3 - 5 - nullpre更新为3。下一组end从pre走 2 步但pre.next是5end只能走到5然后下一步为None发现不足 k 个结束。最终结果为[2,1,4,3,5]。代码实现# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defreverseKGroup(self,head:Optional[ListNode],k:int)-Optional[ListNode]:# 辅助函数翻转整个链表返回新的头defreverseList(node):prevNonecurrnodewhilecurr:next_nodecurr.nextcurr.nextprev prevcurr currnext_nodereturnprev# 新的头# 创建哨兵节点dummyListNode(0,head)predummy# pre 指向每组的前一个节点whileTrue:# 检查剩余节点是否足够 k 个endpreforiinrange(k):endend.nextifnotend:# 不足 k 个返回结果returndummy.next# 记录下一组的起点next_groupend.next# 断开当前组startpre.nextend.nextNone# 翻转当前组new_headreverseList(start)# 翻转后原来的 end 成为新头# 连接前后pre.nextnew_head start.nextnext_group# 更新 pre 到下一组的前一个节点即当前组的尾prestart复杂度分析时间复杂度O(n)其中 n 是链表长度。我们遍历了每个节点一次每组翻转也是 O(k)总体线性。空间复杂度O(1)只使用了常数个额外指针满足进阶要求。总结本题是链表操作中较有难度的一道题主要考察对指针的熟练运用。核心技巧在于使用哨兵节点简化头节点处理。每次先检查剩余节点是否足够再断开、翻转、连接。注意更新pre指针到当前组的末尾以便下一轮循环。空间复杂度O(1)只使用了常数个额外指针满足进阶要求。总结本题是链表操作中较有难度的一道题主要考察对指针的熟练运用。核心技巧在于使用哨兵节点简化头节点处理。每次先检查剩余节点是否足够再断开、翻转、连接。注意更新pre指针到当前组的末尾以便下一轮循环。掌握这个方法后对于类似的分组翻转问题也能迎刃而解。