Python算法题集_K 个一组翻转链表

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

题25：K 个一组翻转链表

1. 示例说明

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

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

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

  示例 1：

  

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

  示例 2：

  

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

  提示：

  • 链表中的节点数目为 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 cfp

class Solution:
 @staticmethod
 def reverseKGroup_base(head, k):
     if head is None or k < 2:
         return head
     tmpnode = head
     for iIdx in range(k - 1):
         tmpnode = tmpnode.next
         if tmpnode is None:
             return head
     headnode = tmpnode
     currnode = head
     while tmpnode:
         prevnode, tailnode = None, currnode
         for iIdx in range(k):
             if tmpnode:
                 tmpnode = tmpnode.next
             nextnode = currnode.next
             currnode.next = prevnode  
             prevnode, currnode = currnode, nextnode  
         tailnode.next = tmpnode or currnode
     return headnode

result = cfp.getTimeMemoryStr(Solution.reverseKGroup_base, ahead, 101)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))

# 运行结果
函数 reverseKGroup_base 的运行时间为 46.01 ms；内存使用量为 4.00 KB 执行结果 = 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

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

马马虎虎，超过64%

import CheckFuncPerf as cfp

class Solution:
 @staticmethod
 def reverseKGroup_ext1(head, k):
     list_node, iIdx = [], 0
     if not head:
         return None
     while head:
         list_node.append(head)
         head = head.next
     while iIdx <= len(list_node) - k:
         list_node[iIdx:iIdx+k] = list_node[iIdx:iIdx+k][::-1]
         iIdx += k
     for jIdx in range(len(list_node) - 1):
         list_node[jIdx].next = list_node[jIdx+1]
     if list_node:
         list_node[-1].next = None
         return 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

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

性能优良，超过82%

import CheckFuncPerf as cfp

class Solution:
 @staticmethod
 def reverseKGroup_ext2(head, k):
     newhead = ListNode(0)
     noderight = newhead
     while True:
         ipos = k
         nodestack = []
         tmpnode = head
         while ipos and tmpnode:
             nodestack.append(tmpnode)
             tmpnode = tmpnode.next
             ipos -= 1
         if ipos:
             noderight.next = head
             break
         while nodestack:
             noderight.next = nodestack.pop()
             noderight = noderight.next
         head = tmpnode
     return newhead.next

result = cfp.getTimeMemoryStr(Solution.reverseKGroup_ext2, ahead, 101)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))

# 运行结果
函数 reverseKGroup_ext2 的运行时间为 78.03 ms；内存使用量为 12.00 KB 执行结果 = 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

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

性能优异，超越96%

import CheckFuncPerf as cfp

class Solution:
 @staticmethod
 def reverseKGroup_ext3(head, k):
     curnode = head
     ipos = 0
     while curnode and ipos != k:
         curnode = curnode.next
         ipos += 1
     if ipos == k:
         curnode = Solution.reverseKGroup_ext3(curnode, k)
         while ipos:
             tmpnode = head.next
             head.next = curnode
             curnode = head
             head = tmpnode
             ipos -= 1
         head = curnode
     return head

result = 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

4. 最优算法

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

nums = [ x for x in range(200000)]
def generateOneLinkedList(data):
    head = ListNode()
    current_node = head
    for num in data:
        new_node = ListNode(num)
        current_node.next = new_node
        current_node = new_node
    return 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

may the odds be ever in your favor ~