文档章节

判断链表是否存在环 Linked List Cycle

叶枫啦啦
 叶枫啦啦
发布于 2017/06/20 18:02
字数 249
阅读 1
收藏 0

问题:

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

Follow up:
Can you solve it without using extra space?

解决:

① 采用快慢指针,fast每次前进2步,slow每次前进1步,若两者相遇,则说明存在环。若fast指向null或者fast的下一个是null,就说明没有环。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

② 使用hash set存储已经遍历过的节点,若有重复,说明存在环,否则不存在。

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

© 著作权归作者所有

叶枫啦啦
粉丝 13
博文 583
码字总数 400448
作品 0
海淀
私信 提问
LeetCode 142. Linked List Cycle II (链表环起点)

Given a linked list, return the node where the cycle begins. If there is no cycle, return . To represent a cycle in the given linked list, we use an integer which represents the......

dby_freedom
2018/12/08
0
0
LeetCode 142:环形链表 II Linked List Cycle II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 。 为了表示给定链表中的环,我们使用整数 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 是 ,则在该链表中...

iCodeBugs
07/17
22
0
[算法][LeetCode] 链表

[算法][LeetCode]Linked List Cycle & Linked List Cycle II——单链表中的环 1.判断链表中是否有环 2.如果有环,找出环的起点 http://www.cnblogs.com/hiddenfox/p/3408931.html 1.快慢指针...

素雷
2017/10/19
4
0
LeetCode 141:环形链表 Linked List Cycle

给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 是 ,则在该链表中没有环。 Given a linked list, det...

iCodeBugs
07/16
19
0
单链表中有环

原题   Given a linked list, determine if it has a cycle in it.   Follow up:   Can you solve it without using extra space? 题目大意   给定一个单链表,判断链表是否有环。 ...

一贱书生
2016/12/23
4
0

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
今天
58
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
今天
27
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
今天
61
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
今天
57
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
今天
50
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部