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;
    }
}

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

微信打赏

支付宝打赏

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

查看所有标签

猜你喜欢:

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

码农书籍

MySQL技术内幕

姜承尧 / 机械工业出版社 / 2013-5 / 79.00元

《MySQL技术内幕:InnoDB存储引擎(第2版)》由国内资深MySQL专家亲自执笔，国内外多位数据库专家联袂推荐。作为国内唯一一本关于InnoDB的专著，《MySQL技术内幕:InnoDB存储引擎(第2版)》的第1版广受好评，第2版不仅针对最新的MySQL 5.6对相关内容进行了全面的补充，还根据广大读者的反馈意见对第1版中存在的不足进行了完善，《MySQL技术内幕:InnoDB存储引擎(第2......一起来看看《MySQL技术内幕》这本书的介绍吧!

码农工具

SHA 加密

SHA 加密工具

HEX HSV 转换工具

HEX HSV 互换工具