Python算法题集_环形链表

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

题234：环形链表

1. 示例说明

• 给你一个链表的头节点 head ，判断链表中是否有环。

  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

  如果链表中存在环 ，则返回 true 。 否则，返回 false 。

  示例 1：

  

  输入：head = [3,2,0,-4], pos = 1
输出：true解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

---

2. 题目解析

- 题意分解

1. 本题为链表的值查重
2. 本题的主要计算有2处，1是链表遍历，2是值比较
3. 基本的解法是单层循环，必须读取链表数据后进行检测，所以基本的时间算法复杂度为O(n）

- 优化思路

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

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

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

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

   1. 链表需要遍历中进行值检查，为提高检索速度，可以采用哈希检索，采用set、dict等数据结构

   2. 空间复杂度为O(1)的算法，一般是需要用到快慢双指针

---

- 测量工具

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

---

3. 代码展开

1) 标准求解【集合检索】

采用集合set进行值检索

性能优良，超过88

import CheckFuncPerf as cfpdef hasCycle_base(head):set_checked = set()  while head: if head in set_checked:return Trueset_checked.add(head)  head = head.next  return Falseresult = cfp.getTimeMemoryStr(hasCycle_base, head1)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 运行结果
函数 hasCycle_base 的运行时间为 27.01 ms；内存使用量为 996.00 KB 执行结果 = True

2) 改进版一【字典检测】

采用字典dict进行值检索，由于字典分配内存远大于集合，因此哈希检索的效率要低一些

马马虎虎，超过64%

import CheckFuncPerf as cfpdef hasCycle_ext1(head):dict_checked = {} while head:  dict_checked[head] = dict_checked.get(head, 0)if dict_checked[head] == 1:return Truedict_checked[head] = 1head = head.next return Falseresult = cfp.getTimeMemoryStr(hasCycle_ext1, head1)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 运行结果
函数 hasCycle_ext1 的运行时间为 58.00 ms；内存使用量为 128.00 KB 执行结果 = True

3) 改进版二【双指针】

没有很多内存分配的事，空间复杂度好的算法，时间复杂度也很好
表现优异，超越95%

import CheckFuncPerf as cfpdef hasCycle_ext2(head):slownode , fastnode = head, headwhile fastnode and fastnode.next:slownode = slownode.nextfastnode = fastnode.next.nextif slownode == fastnode:breakif fastnode and fastnode.next:while head != slownode:head = head.nextslownode = slownode.nextreturn Trueelse:return Falseresult = cfp.getTimeMemoryStr(hasCycle_ext2, head1)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 运行结果
函数 hasCycle_ext2 的运行时间为 30.01 ms；内存使用量为 0.00 KB 执行结果 = True

---

4. 最优算法

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

# 超时测试
nums = [x for x in range(200000)]
def generateOneLinkedList(data):head = ListNode(-100)iPos = 0current_node = headfor num in data:iPos += 1if iPos == 190000:CycleNode = new_nodenew_node = ListNode(num)current_node.next = new_nodecurrent_node = new_nodenew_node.next = CycleNodereturn head.next, new_node
head1, tail1 = generateOneLinkedList(nums)result = cfp.getTimeMemoryStr(hasCycle_base, head1)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 算法本地速度实测比较
函数 hasCycle_base 的运行时间为 27.01 ms；内存使用量为 996.00 KB 执行结果 = True
函数 hasCycle_ext1 的运行时间为 58.00 ms；内存使用量为 128.00 KB 执行结果 = True
函数 hasCycle_ext2 的运行时间为 30.01 ms；内存使用量为 0.00 KB 执行结果 = True

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

may the odds be ever in your favor ~