当前位置:网站首页>笔试面试题目:判断单链表是否有环

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

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