Python算法题集_排序链表

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

题148：排序链表

1. 示例说明

• 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

  示例 1：

  

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

  示例 2：

  

  输入：head = [-1,5,3,4,0]
  输出：[-1,0,3,4,5]
  

  示例 3：

  输入：head = []
  输出：[]
  

  提示：

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

  **进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

---

2. 题目解析

- 题意分解

1. 本题为对链表进行排序
2. 基本的解法是双层循环冒泡法，所以基本的时间算法复杂度为O(n^2）

- 优化思路

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

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

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

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

   1. 链表的排序算法极为耗时

   2. 可以采用归并法对链表进行拆分然后合并

   3. 可以用列表排序法进行简单排序

---

- 测量工具

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

---

3. 代码展开

1) 标准求解【冒泡大法】

链表双层，每次循环将一个最大值移到尾部，毫无意外的超时

无法通关，果然超时

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_base(head):if not head:return headif not head.next:return headbexchange = Truetmphead = ListNode(-1)tmphead.next = headtmpNode = tmpheadwhile bexchange and tmpNode:bexchange = FalsestartNode = tmpNodewhile startNode:if startNode.next:nextnode = startNode.nextif startNode.next.next:nextnode2 = nextnode.nextif nextnode.val > nextnode2.val:tmpNext = nextnode2.nextstartNode.next = nextnode2nextnode2.next = nextnodenextnode.next = tmpNextbexchange = TruestartNode = startNode.nextreturn tmphead.nextresult = cfp.getTimeMemoryStr(Solution.sortList_base, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果【链表长度1W】
函数 sortList_base 的运行时间为 20534.61 ms；内存使用量为 4.00 KB 执行结果 = 1

2) 改进版一【列表排序】

将链表存入列表结构，通过列表排序，最后再连接起来，性能优异，内存O(n)

性能卓越，超越96%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_ext1(head):if not head:return headif not head.next:return headlist_node = []while head:list_node.append([head.val, head])head = head.nextsort_list = sorted(list_node, key=lambda x: x[0])for iIdx in range(len(sort_list)-1):sort_list[iIdx][1].next = sort_list[iIdx+1][1]sort_list[-1][1].next = Nonereturn sort_list[0][1]result = cfp.getTimeMemoryStr(Solution.sortList_ext1, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果【链表长度1W】
函数 sortList_ext1 的运行时间为 2.99 ms；内存使用量为 16.00 KB 执行结果 = 1

3) 改进版二【数值归并排序】

使用递归设计，用值定位将链表拆分排序；递归的最大层次为990，因此链表长度在2^990次方内都不会溢出

不值一提，超过06%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_ext2(head):if not head:return headmin_val = max_val = head.valcurnode = headwhile curnode:min_val = min(min_val, curnode.val)max_val = max(max_val, curnode.val)curnode = curnode.nextif min_val == max_val:return headmid_val = (min_val + max_val) // 2head1 = ListNode(0) last1 = head1 head2 = ListNode(0) last2 = head2 curnode = headwhile curnode:if curnode.val <= mid_val:last1.next = curnodelast1 = last1.next else:last2.next = curnodelast2 = last2.nextcurnode = curnode.next last1.next = Nonelast2.next = None head1 = Solution.sortList_ext2(head1.next) head2 = Solution.sortList_ext2(head2.next)curnode = head1while curnode.next:curnode = curnode.nextcurnode.next = head2return head1result = cfp.getTimeMemoryStr(Solution.sortList_ext2, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 sortList_ext2 的运行时间为 71.03 ms；内存使用量为 0.00 KB 执行结果 = 1

4) 改进版三【快慢指针归并排序】

使用递归设计，用快慢指针将链表拆分排序；递归的最大层次为990，因此链表长度在2^990次方内都不会溢出

马马虎虎，超越72%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_ext3(head):if not head or not head.next:return headslownode, fastnode = head, head.nextwhile fastnode and fastnode.next:fastnode, slownode = fastnode.next.next, slownode.nextmidnode, slownode.next = slownode.next, None leftlink, rightlink = Solution.sortList_ext3(head), Solution.sortList_ext3(midnode)tmpnode = headnode = ListNode(0)while leftlink and rightlink:if leftlink.val < rightlink.val:tmpnode.next, leftlink = leftlink, leftlink.nextelse:tmpnode.next, rightlink = rightlink, rightlink.nexttmpnode = tmpnode.nexttmpnode.next = leftlink if leftlink else rightlinkreturn headnode.nextresult = cfp.getTimeMemoryStr(Solution.sortList_ext3, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 sortList_ext3 的运行时间为 19.02 ms；内存使用量为 0.00 KB 执行结果 = 1

---

4. 最优算法

根据本地日志分析，最优算法为第2种sortList_ext1，如果内存要O(1)的话，则最优算法为第4种sortList_ext3

iLen = 10000
nums = [iLen - x for x in range(iLen)]
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.sortList_base, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 算法本地速度实测比较
函数 sortList_base 的运行时间为 20534.61 ms；内存使用量为 4.00 KB 执行结果 = 1
函数 sortList_ext1 的运行时间为 2.99 ms；内存使用量为 16.00 KB 执行结果 = 1
函数 sortList_ext2 的运行时间为 71.03 ms；内存使用量为 0.00 KB 执行结果 = 1
函数 sortList_ext3 的运行时间为 19.02 ms；内存使用量为 0.00 KB 执行结果 = 1

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

may the odds be ever in your favor ~