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

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

创新互联公司成都企业网站建设服务，提供做网站、成都网站制作网站开发,网站定制,建网站,网站搭建,网站设计,成都响应式网站建设,网页设计师打造企业风格网站,提供周到的售前咨询和贴心的售后服务。欢迎咨询做网站需要多少钱:18980820575

为啥要刷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中怎么判断链表是否有环了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注创新互联行业资讯频道。

网页名称：leetcode中怎么判断链表是否有环
文章链接：https://www.cdcxhl.com/article10/pjjhdo.html

成都网站建设公司_创新互联，为您提供网站制作、用户体验、服务器托管、小程序开发、网站内链、网站收录

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联