当前位置:网站首页>笔试面试题目:判断单链表是否有环
笔试面试题目:判断单链表是否有环
2020-11-08 10:30:00 【osc_ezb5qfcz】
原文发表于:
之前在U公司的笔试中,碰到这样一个问题:
判断单链表是否有环。
首先来看这样一个常识:现实中的环路与单链表的环路,有什么不同呢?
显然:现实中的环路,可以有两个方向,要么循环,要么逃出。然而,在单链表中,指针next只可能有一个指向,所以环路链表必定永远循环,没有出口。如下图所示:
回到问题本身,怎么判断单链表是否有环呢?
算法1:标记法
最容易想到的肯定是标记法。遍历链表时,对访问过的结点做记录。如果是环状单链表,则必然有结点被重复访问。这种思路是非常自然的。
做标记时,可考虑用hash map或者hash set, 需要耗费一些空间。由于思路比较明确,所以就没有必要详细介绍程序了。
算法2:暴力算法
暴力,也是解决问题的一种思路,尽管不一定是最好的方式。
可以这么考虑:一路走到黑,如果到了终点,则没有环,如果没有到达终点,则说明在环中不停绕圈。
我刚才在leetcode上做了一下这个题目,用的是暴力法,能通过所有测试用例,代码如下:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
count := 0
max := 12000
for ; head != nil && count < max; {
count++
head = head.Next
}
if count == max {
return true
}
return false
}
一看就知道,这种暴力算法是有局限性的:比如,如果链表足够长,也会导致count和max相等,可能会误判的。
算法3:快慢指针
摩托车在后,自行车在前,摩托车追赶自行车,如果是一个没有出路的环形路,那么摩托车必然会追上自行车。
所以,我们可以采用类似思路,让快指针在后,慢指针在前,可以判断单链表是否带环。这种方法的好处是,空间复杂度是O(1),且不会出现误判。
既然知道了思路,写程序就是很简单的事情了,故不再赘述。
周末愉快,下周再聊,不见不散。
版权声明
本文为[osc_ezb5qfcz]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4309139/blog/4707995
边栏推荐
- Basic concepts of computer network (5) basic principles of local area network
- How can a technician take over a complex system?
- The young generation of winner's programming life, the starting point of changing the world is hidden around
- 将“光头”识别为“足球”,AI 摄像头如何犯的错?
- ArrayList源码分析
- Rust:命令行参数与环境变量操作
- Tiktok live monitoring Api: random recommendation
- Flink's sink: a preliminary study
- 不多不少,大学里必做的五件事(从我的大一说起)
- 游戏优化性能杂谈(十一) - 知乎
猜你喜欢
狗狗也能操作无人机!你没看错,不过这其实是架自动驾驶无人机 - 知乎
Astra: Apache Cassandra的未来是云原生
[original] about the abnormal situation of high version poi autosizecolumn method
Rust: command line parameter and environment variable operation
How can a technician take over a complex system?
Seven features of Python 3.9
Oschina plays on Sunday - before that, I always thought I was a
Visual Studio 2015 未响应/已停止工作的问题解决
Game optimization performance (11) - Zhihu
SQL Server 2008R2 18456错误解决方案
随机推荐
M-end software product design considerations - Zhihu
Bili Bili common API
How TCP protocol ensures reliable transmission
成功解决An error ocurred while starting the kernel
211 postgraduate entrance examination failed, stay up for two months, get the byte offer! [face to face sharing]
Oschina plays on Sunday - before that, I always thought I was a
Solve Safari browser download file name garbled problem
YGC问题排查,又让我涨姿势了!
What is the difference between vivoy73s and vivoy70s
Flink's sink: a preliminary study
维图PDMS切图软件
来自不同行业领域的50多个对象检测数据集
VC++指定目录下文件按时间排序输出
Mate 40 series launch with Huawei sports health service to bring healthy digital life
More than 50 object detection datasets from different industries
vivoS7e和vivoS7的区别 哪个更值得入手
Improvement of rate limit for laravel8 update
nvm
C++在C的基础上改进了哪些细节
2020-11-05