【Python】寻找链表里的环的最短实践

lewinlee 发布于2019-07-25 10:46 / 1459人阅读

摘要：背景在上刷题碰到检测链表里环的长度必定有环，构思出一个很短的函数。题目描述解题思路在代码处一目了然代码感想真是一个十分好用的数据结构。

背景

在Codewar上刷题碰到检测链表里环的长度（必定有环），构思出一个很短的函数。

题目描述、解题思路

在代码处一目了然

代码

def loop_size(node):
    past, length = {}, 0
    while past.get(node, None) is None: past[node], length, node = length, length + 1, node.next
    return length - past[node]

感想

dict真是一个十分好用的数据结构。

服务器托管云服务器最短寻找时间优先和电梯调度算法 python编程实践 python实践项目 python项目实践

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/38151.html

链表中环的入口节点

摘要：题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出。题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = va...

qpal 2019-08-16 18:28 评论0 收藏0
写一段代码判断单向链表中有没有形成环，如果形成环，请找出环的入口处，即P点

摘要：由于要比移动的快，如果有环，一定会先进入环，而后进入环。现在问题就简单了，由于移动的距离永远是的一般，因此当遍历玩整个环长度个节点的时候正好遍历了个节点，也就是说，此时正好指向距离最远的点。首先，关于单链表中的环，一般涉及到以下问题： 1.给一个单链表，判断其中是否有环的存在； 2.如果存在环，找出环的入口点； 3.如果存在环，求出环上节点的个数； 4.如果存在环，求出链表的长度； ...

OldPanda 2019-07-01 13:56 评论0 收藏0
算法第四版4.1-无向图详解

摘要：树是一副无环连通图。互不相连的树组成的集合称为森林。表示无向图的数据类型图的基本操作的两个构造，得到顶点数和边数，增加一条边。该方法不符合第一个条件，上百万个顶点的图是很常见的空间不满足。四种重要的图模型：无向图（简单连接）有向图（连接有方向性）加权图（连接带有权值）加权有向图（连接既有方向性又带有权值）无向图定义：由一组顶点和一组能够将两个顶点相连的边组成。特殊：...

scola666 2019-08-14 17:53 评论0 收藏0