笔试面试题目：判断单链表是否有环

       原文发表于：

 

      之前在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)，且不会出现误判。

      既然知道了思路，写程序就是很简单的事情了，故不再赘述。

 

 

      周末愉快，下周再聊，不见不散。