python判断单向链表是否包括环,若包含则计算环入口的节点实例分析
Python  /  管理员 发布于 6年前   141
本文实例讲述了python判断单向链表是否包括环,若包含则计算环入口的节点。分享给大家供大家参考,具体如下:
关于数据结构相关的面试题,经常会问到链表中是否存在环结构的判断,下图就是存在环结构的链表。
那么如何判断链表中是否存在环呢,下面解法的思路是采用快慢指针:
两个指向头节点的指针,fast和slow,一起从头结点开始往后遍历,fast每次移动两个节点,slow每次移动一个节点,
这样,如果存在环结构,那么fast指针在不断绕环过程中,肯定会追上slow指针。
# -*- coding:utf-8 -*-'''Created on 2019年10月23日@author: Administrator'''class Node(): #定义一个Node类,构造两个属性,一个是item节点值,一个是节点的下一个指向 def __init__(self,item=None): self.item = item self.next = Nonedef findbeginofloop(head):#判断是否为环结构并且查找环结构的入口节点 slowPtr = head #将头节点赋予slowPtr fastPtr = head #将头节点赋予fastPtr loopExist =False #默认环不存在,为False if head == None: #如果头节点就是空的,那肯定就不存在环结构 return False while fastPtr.next != None and fastPtr.next.next != None: #fastPtr的下一个节点和下下个节点都不为空 slowPtr = slowPtr.next #slowPtr每次移动一个节点 fastPtr = fastPtr.next.next #fastPtr每次移动两个节点 if slowPtr == fastPtr : #当fastPtr和slowPtr的节点相同时,也就是两个指针相遇了 loopExist = True print("存在环结构") break if loopExist == True: slowPtr = head while slowPtr != fastPtr: fastPtr = fastPtr.next slowPtr = slowPtr.next return slowPtr print("不是环结构") return Falseif __name__ == "__main__": node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 node5.next = node2 print(findbeginofloop(node1).item)
运行结果:
存在环结构
2
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
123 在
Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..原梓番博客 在
在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..博主 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..1111 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..路人 在
php中使用hyperf框架调用讯飞星火大模型实现国内版chatgpt功能示例中评论 教程很详细,如果加个前端chatgpt对话页面就完美了..Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号