本文主要是介绍笔试面试题目：判断单链表是否有环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原文发表于：
之前在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 := 0max := 12000for ; head != nil && count < max; {count++head = head.Next}if count == max {return true}return false
}一看就知道，这种暴力算法是有局限性的：比如，如果链表足够长，也会导致count和max相等，可能会误判的。
算法3：快慢指针
摩托车在后，自行车在前，摩托车追赶自行车，如果是一个没有出路的环形路，那么摩托车必然会追上自行车。
所以，我们可以采用类似思路，让快指针在后，慢指针在前，可以判断单链表是否带环。这种方法的好处是，空间复杂度是O(1)，且不会出现误判。
既然知道了思路，写程序就是很简单的事情了，故不再赘述。
周末愉快，下周再聊，不见不散。
这篇关于笔试面试题目：判断单链表是否有环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
