本文为Python算法题集之一的代码示例

题25：K 个一组翻转链表

1. 示例说明

• 给你链表的头节点 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]
  

  提示：

  • 链表中的节点数目为 n

    • 1 <= k <= n <= 5000
    • 0 <= Node.val <= 1000

    **进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

---

2. 题目解析

- 题意分解

1. 本题为对链表中的节点进行块反转
2. 本题的主要计算是2块，1是链表遍历，2是节点反转
3. 基本的解法是单层循环，链表读一遍，过程中执行节点反转，所以基本的时间算法复杂度为O(m）

- 优化思路

1. 通常优化：减少循环层次

2. 通常优化：增加分支，减少计算集

3. 通常优化：采用内置算法来提升计算速度

4. 分析题目特点，分析最优解

   1. 标准方法是一次循环，依次进行块反转

   2. 可以用列表结构进行节点调整，列表结构简单，方便维护

   3. 可以用堆栈法进行块反转

   4. 可以用递归法进行块反转

---

- 测量工具

• 本地化测试说明：LeetCode网站测试运行时数据波动很大，因此需要本地化测试解决这个问题
• CheckFuncPerf（本地化函数用时和内存占用测试模块）已上传到CSDN，地址：Python算法题集_检测函数用时和内存占用的模块
• 本题很难超时，本地化超时测试用例自己生成，详见【最优算法章节】

---

3. 代码展开

1) 标准求解【依次反转】

一次遍历，依次完成块反转

性能优异，超越92%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef reverseKGroup_base(head, k):if head is None or k < 2:return headtmpnode = headfor iIdx in range(k - 1):tmpnode = tmpnode.nextif tmpnode is None:return headheadnode = tmpnodecurrnode = headwhile tmpnode:prevnode, tailnode = None, currnodefor iIdx in range(k):if tmpnode:tmpnode = tmpnode.nextnextnode = currnode.nextcurrnode.next = prevnode  prevnode, currnode = currnode, nextnode  tailnode.next = tmpnode or currnodereturn headnoderesult = cfp.getTimeMemoryStr(Solution.reverseKGroup_base, ahead, 101)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 reverseKGroup_base 的运行时间为 46.01 ms；内存使用量为 4.00 KB 执行结果 = 100

2) 改进版一【列表反转】

将链表转换为数组，再完成节点块反转

马马虎虎，超过64%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef reverseKGroup_ext1(head, k):list_node, iIdx = [], 0if not head:return Nonewhile head:list_node.append(head)head = head.nextwhile iIdx <= len(list_node) - k:list_node[iIdx:iIdx+k] = list_node[iIdx:iIdx+k][::-1]iIdx += kfor jIdx in range(len(list_node) - 1):list_node[jIdx].next = list_node[jIdx+1]if list_node:list_node[-1].next = Nonereturn list_node[0]result = cfp.getTimeMemoryStr(Solution.reverseKGroup_ext1, ahead, 101)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 reverseKGroup_ext1 的运行时间为 51.03 ms；内存使用量为 156.00 KB 执行结果 = 100

3) 改进版二【堆栈大法】

遍历链表过程中，使用堆栈大法完成节点块反转

性能优良，超过82%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef reverseKGroup_ext2(head, k):newhead = ListNode(0)noderight = newheadwhile True:ipos = knodestack = []tmpnode = headwhile ipos and tmpnode:nodestack.append(tmpnode)tmpnode = tmpnode.nextipos -= 1if ipos:noderight.next = headbreakwhile nodestack:noderight.next = nodestack.pop()noderight = noderight.nexthead = tmpnodereturn newhead.nextresult = cfp.getTimeMemoryStr(Solution.reverseKGroup_ext2, ahead, 101)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 reverseKGroup_ext2 的运行时间为 78.03 ms；内存使用量为 12.00 KB 执行结果 = 100

4) 改进版三【递归大法】

采用递归方式遍历链表，完成节点块反转

性能优异，超越96%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef reverseKGroup_ext3(head, k):curnode = headipos = 0while curnode and ipos != k:curnode = curnode.nextipos += 1if ipos == k:curnode = Solution.reverseKGroup_ext3(curnode, k)while ipos:tmpnode = head.nexthead.next = curnodecurnode = headhead = tmpnodeipos -= 1head = curnodereturn headresult = cfp.getTimeMemoryStr(Solution.reverseKGroup_ext3, ahead, 101)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
Traceback (most recent call last):......
[Previous line repeated 991 more times]
RecursionError: maximum recursion depth exceeded

---

4. 最优算法

根据本地日志分析，最优算法为第3种swapPairs_ext2

nums = [ x for x in range(200000)]
def generateOneLinkedList(data):head = ListNode()current_node = headfor num in data:new_node = ListNode(num)current_node.next = new_nodecurrent_node = new_nodereturn head.next
ahead = generateOneLinkedList(nums)
result = cfp.getTimeMemoryStr(Solution.reverseKGroup_base, ahead, 101)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 算法本地速度实测比较
函数 reverseKGroup_base 的运行时间为 46.01 ms；内存使用量为 4.00 KB 执行结果 = 100
函数 reverseKGroup_ext1 的运行时间为 51.03 ms；内存使用量为 156.00 KB 执行结果 = 100
函数 reverseKGroup_ext2 的运行时间为 78.03 ms；内存使用量为 12.00 KB 执行结果 = 100
Traceback (most recent call last):    # 递归法reverseKGroup_ext3报错......[Previous line repeated 991 more times]
RecursionError: maximum recursion depth exceeded

一日练，一日功，一日不练十日空

may the odds be ever in your favor ~