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

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

微信打赏

支付宝打赏

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

查看所有标签

猜你喜欢:

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

码农书籍

算法竞赛入门经典

刘汝佳 / 清华大学出版社 / 2009-11 / 24.00元

《算法竞赛入门经典》是一本算法竞赛的入门教材，把C/C++语言、算法和解题有机地结合在了一起，淡化理论，注重学习方法和实践技巧。全书内容分为11章，包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、基础题目选解、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、图论模型与算法，覆盖了算法竞赛入门所需的主要知识点，并附有大量习题。书中的代码规范、简洁、易懂，不仅能帮助......一起来看看《算法竞赛入门经典》这本书的介绍吧!

码农工具

JSON 在线解析

在线 JSON 格式化工具

RGB HSV 转换

RGB HSV 互转工具