我要招人

去企业版

首页 > 试题广场 >

判断链表中是否有环

[编程题]判断链表中是否有环

热度指数：513588 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

数据范围：链表长度 $0 \le n \le 10000$ ，链表中任意节点的值满足 $|val| <= 100000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：

可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。

示例1

输入

{3,2,0,-4},1

输出

true

说明

第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true

示例2

输入

{1},-1

输出

false

说明

第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false

示例3

输入

{-1,-7,7,-4,19,6,-9,-5,-2,-5},6

输出

true

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Maokt

发表于 2021-07-05 10:14:44

精华题解算法思想一：双指针解题思路：我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。图解：展开全文

牛客题解官

发表于 2022-04-22 11:24:19

精华题解题目主要信息: 给定一个链表的头节点，判断这个链表是否有环环形链表如下所示：举一反三：学习完本题的思路你可以解决如下题目： BM4.合并有序链表 BM5.合并k个已排序的链表 BM7.链表中环的入口节点 BM8.链表中倒数最后k个节点 BM9.删除链表的倒数第n个节点 BM10.两个链表展开全文

leaves0924

发表于 2021-07-17 00:43:20

精华题解题目描述判断给定的链表中是否有环。如果有环则返回true，否则返回false。你能给出空间复杂度的解法么？输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试示例1输入：{3,2,0, 展开全文

牛一霸

发表于 2021-07-02 00:07:09

精华题解题目：判断链表中是否有环描述：判断给定的链表中是否有环。如果有环则返回true，否则返回false。你能给出空间复杂度的解法么？输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读展开全文

Peterliang

发表于 2021-07-16 12:50:55

精华题解题意分析这个题目是NC3的弱化版，这个题目不需要我们求出环的入口结点，只需要我们判断是否存在环就可以。思路分析所以我们可以按照NC3那题的思路来写。思路一哈希处理我们首先将所有的结点存入一个哈希表里面，然后我们需要遍历整个链表，如果存在相同的节点说明存在环，返回true即可。展开全文

数据结构和算法

发表于 2020-12-21 17:10:00

1，快慢指针解决判断链表是否有环应该是老生常谈的一个话题了，最简单的一种方式就是快慢指针，慢指针针每次走一步，快指针每次走两步，如果相遇就说明有环，如果有一个为空说明没有环。代码比较简单 public boolean hasCycle(ListNode head) { if (head = 展开全文

一只弱小的Kid

发表于 2020-09-04 10:15:01

解法快慢指针的解法，一个指针走两步一个指针走一步，如果快指针直接到了null 说明没有环，如果有环的话总有一次结果会让快指针和慢指针相等。代码 /** * Definition for singly-linked list. * class ListNode { * int 展开全文

王清楚

发表于 2020-12-17 16:33:08

没有环的链表尾节点会指向空有环的链表会有一个节点指向链表中以存在的节点链表如果没有环的话，我们顺着链表的节点一直走下去，一定会遇到空节点。但是如果有环的话，我们一直顺着链表的节点走下去，就会造成死循环，那我们如何判断链表中是否有环呢？设置两个指针，一个指针一次走一步，另一个指针一次走两步,如果两个指展开全文

seaalan

发表于 2021-10-04 10:38:09

给访问过的节点设置标志位，如果再次访问到有标志位的节点，则证明链表中有环。 /* * function ListNode(x){ * this.val = x; * this.next = null; * } */ /** * * @param head ListNode类展开全文

派仔

发表于 2021-06-23 16:40:16

public class Solution { public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast ! 展开全文

总之就是非常可爱

发表于 2021-09-26 11:46:44

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} 展开全文

牛客410632071号

发表于 2022-04-05 17:56:01

哈希表法 #include<stdbool.h> #define base 769 typedef struct ListNode datatype; struct hashlist { datatype key; struct hashlist* Next; }; t 展开全文

helloRachel

发表于 2021-04-09 10:32:26

解题思路遍历一次链表，在遍历的过程中对每一个节点进行标记--是否已被访问，因为空间复杂度要求O(1)，不允许开辟新的空间，因此不能用hash存储，因此我直接将节点的值用一个固定的数字标识，一开始用-1标识，有1/15的样例不通过，结果发现val范围在10^-5~10^5，因此考虑到五位数字不会超出展开全文

柿子__

发表于 2022-10-31 00:53:18

解析用Hash表，遍历链表节点，先判断表中是否已经存在。如果存在就是证明有环，不存在就将节点保存进Hash表，直到遍历到nullptr证明没有环。代码 bool hasCycle(ListNode *head) { unordered_set<List 展开全文

s摸鱼大师s

发表于 2022-01-13 19:09:46

class Solution { public: bool hasCycle(ListNode *head) { //链表不为空 if(head == nullptr || head->next == nullptr ) { return fal 展开全文

问题信息

链表哈希双指针

难度：

572条回答 1291收藏 49701浏览

通过挑战的用户

查看代码

牛客11552...

2023-03-14 10:43:28
酷酷的方呀

2023-02-26 20:37:13
牛客57017...

2023-02-16 21:40:25
随机昵称都有什...

2023-02-10 17:05:31
1881006...

2023-02-08 17:10:03

判断链表中是否有环

输入

输出

说明

输入

输出

说明

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题