在判断是否有环前,需要先知道什么是链表中的环?
如下所示的链表有5个节点组成,框内的数字代表编号,也可理解为节点的地址。注意区分地址值和链表的数据域是完全不同的:
节点0指向节点3,而节点10又指向节点3,所以节点3就是环的入口,形成如下所示的一个环:
如果像下面这样遍历一个有环链表:
# head 是链表的头
while head:
print(head.data)
head = head.next
程序将会进入死循环,会在环内无穷的跑下去。
所以,研究如何判断链表是否有环,是一个非常有意义的课题,也是面试中常考的。
通过哈希的方法,代码比较好理解:
class Solution(object):
def hasCycle(self, head):
s = set()
tmp = head
while tmp:
if tmp in s:
return True
s.add(tmp)
tmp = tmp.next
return False
今天主要分析如何使用快慢指针判断链表是否有环,做到O(1)
的空间复杂度,O(n)
的时间复杂度,因此比哈希方法要更加节省内存空间。
快慢指针判断链表是否有环,代码其实非常清晰,但是理解背后的数学原理,才是真正写出代码的关键,也就说一旦理解原理,就会很自然的写出代码;相反,如果不理解,仅仅凭记忆,那么时间长了,就容易忘记,面试时就容易写错。
今天,重点也是理解背后的数学原理,下面这个视频参考网络,讲解的非常清晰,大家不妨看一遍:
代码网络上一搜有很多,在这里就不再贴了。
本文分享自 程序员郭震zhenguo 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!