141. 环形链表

栏目: 数据库 · 发布时间: 5年前

内容简介：版权声明：本文为博主原创文章，发表自知一的指纹。转载需向给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

正常的解题思路，通过记录走过的节点来判断是否有环。

时间复杂度：O(n)，对于含有 n 个元素的链表，我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1) 的时间。

空间复杂度：O(n)，空间取决于添加到哈希表中的元素数目，最多可以添加 n 个元素。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<Integer> points = new HashSet<Integer>();
        ListNode cur = head;
        while (null != cur){
            int curHashCode = cur.hashCode();
            if(points.contains(curHashCode)){
                return true;
            }
            points.add(curHashCode);
            cur = cur.next;
        }
        return false;
    }
}

第二种解题思路是双指针大小步，一个指针每次走一步，另一个指针每次走两步，如果有环的话则两个指针最终会相遇。

在最糟糕的情形下，时间复杂度为 O(N+K)，也就是 O(n)。

空间复杂度：O(1)，我们只使用了慢指针和快指针两个结点，所以空间复杂度为 O(1)。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (null == head){
            return false;
        }else if (null == head.next){
            return false;
        }else if (head == head.next.next){
            return true;
        }
        ListNode minCur = head.next;
        ListNode maxCur = head.next.next;
        while (minCur != maxCur){
            if (null == minCur.next){
                return false;
            }else if (null == maxCur.next){
                return false;
            }else if (null == maxCur.next.next){
                return false;
            }
            minCur = minCur.next;
            maxCur = maxCur.next.next;
            if (minCur == maxCur){
                return true;
            }
        }
        return false;
    }
}

如果此文章能给您带来小小的提升，不妨小额赞赏我一下，以鼓励我写出更好的文章！

微信打赏

支付宝打赏

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

HTML和XHTML权威指南(第五版)

Chuck Musciano、Bill Kennedy / 技桥 / 清华大学出版社 / 2004-6-1 / 72.00元

HTML！XHTML！级联样式表！编写网页的标准很难整理，因为各种版本的Netscape和Internet Explorer在其实现方式上千差万别。《HTML与XHTML权威指南》将这些标准全部介绍给了读者。本书作者找出了各种标准和浏览器特性，并在创建网页方面为读者提出了很多建议，以便能够被更广泛的浏览者和平台所接受。学习HTML或XHTML和学习其他任何语言一样。大部分学生都是从......一起来看看《HTML和XHTML权威指南(第五版)》这本书的介绍吧!

码农工具

141. 环形链表

HTML和XHTML权威指南(第五版)

随机密码生成器

RGB HSV 转换

HEX CMYK 转换工具