leetcode中怎么判断链表是否有环

这期内容当中小编将会给大家带来有关leetcode中怎么判断链表是否有环，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

为啥要刷leetcode？

数据结构表征数据存储的格式及操作数据的方式，了解这些便于我们大数据开发人员设计更好的存储，读取，计算策略。所以在java基础，大数据基础，大数据框架源码等都有一定基础之后应该去追求写出更加精致高效的代码。

最近，在整理java面试题，发现很多java底层，redis的有序set等存储结构，spark ，mr等等等我们常用的工具常见的框架都用到了数据结构与算法。所以，要想彻底搞明白底层原理，编写处时间复杂度比较低的代码，还是要去刷一下数据结构，况且数据结构貌似是bat 数据技术类必须面试的门槛，当然你做平台开发最好也会，不要以为用不到就不去学，只是你还比较菜。

再回到为啥要刷一下leetcode？

老外都在刷，大学生也在刷，自己不刷刷，大数据搞的再好有毛用，也只是底层开发。

此处，应该吐血。。。

于是乎，今天leetcode破处了，第一个题是以前没搞明白的一个题。题目如下：

Given a linked list, determine if it has a cycle in it.

就是给定一个链表如何判断其中有环。leetcode给出的命题及案例如下：

第一次是毕业的时候面试被问到这个题，一脸懵逼，这不刷题谁会？

最近细思大致思路有三：

1. 穷举。从头遍历到尾，发现指向null，说明没环。这明显不靠谱。。。时间复杂度O(n)

2. 第三方存储。边遍历边将指针存入hashset，并且判断当前指针是否存在于hashset，假如存在确定有环。否则无环。时间复杂度O(n)。

   
   

   public boolean hasCycle(ListNode head) {
       Set<ListNode> nodesSeen = new HashSet<>();
       while (head != null) {
           if (nodesSeen.contains(head)) {
               return true;
           } else {
               nodesSeen.add(head);
           }
           head = head.next;
       }
       return false;
   }

    

3. 快慢指针。快指针每次走两步，慢指针走一步。假如无环，慢指针永远无法追上快指针，时间复杂度就是O(n)。假如有环，那么快指针会先掉进环里，在那打圈转，快慢指针会相遇。leetcode 上编写的java代码如下：

ListNode walker = head;
        ListNode runner = head;
        while(runner!=null&&runner.next!=null){
            walker = walker.next;
            runner = runner.next.next;
            if(walker == runner){
                return true;
            }
        }
        return false;

上述就是小编为大家分享的leetcode中怎么判断链表是否有环了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注亿速云行业资讯频道。