首页 > 其他分享 >判断链表中是否有环

判断链表中是否有环

时间:2023-05-07 14:12:40浏览次数:57  
标签:结点 判断 ListNode fast 链表 有环 指针

  • 描述
判断给定的链表中是否有环。如果有环则返回true,否则返回false。   数据范围:链表长度 0≤n≤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  
  • 算法思想

1、设置快慢两个指针,初始都指向链表头。

2、遍历链表,快指针每次走两步,慢指针每次走一步。

3、如果快指针到了链表末尾,说明没有环,因为它每次走两步,所以要验证连续两步是否为NULL。

4、如果链表有环,那快慢双指针会在环内循环,因为快指针每次走两步,因此快指针会在环内追到慢指针,二者相遇就代表有环。

 

  • 代码
 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     bool hasCycle(ListNode *head) {
12         ListNode *slow=head;
13         ListNode *fast=head;
14         //使用快慢指针
15         while(fast&&fast->next){
16             fast=fast->next->next;
17             slow=slow->next;
18             if(fast==slow)
19             return true;
20         }
21         return false;
22     }
23 };

 

参考:题解 | #判断链表中是否有环#_牛客博客 (nowcoder.net)

 

标签:结点,判断,ListNode,fast,链表,有环,指针
From: https://www.cnblogs.com/yueshengd/p/17379238.html

相关文章

  • 力扣《环形链表Ⅱ》超详细题解
    作为经典题目的《环形链表Ⅱ》,我认为这题还是有专门出一期博客的分量的,大家也可以自己事先按照自己的理解写一写,然后再来看题解,毕竟自己悟出来的东西是比吸收别人的来的更深刻。一、题目给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。......
  • 练习:判断字符串是否与给定的正规式匹配
    代码写完后应该是这个效果:控制台键入“./a.exe'a(b|c)*d'acbcd<回车>”,可以看到控制台显示“True”。大致流程:判断参数个数,参数不够就给出提示。分析正规式的正确性。合法字符是数字、英文字母大小写、下划线、左右小括号、竖线“|”和星号“*”。用树结构存储正规式。对......
  • BM3 链表中的节点每k个一组翻转
    描述将给出的链表中的节点每k 个一组翻转,返回翻转后的链表如果链表中的节点数不是k的倍数,将最后剩下的节点保持原样你不能更改节点中的值,只能更改节点本身。 数据范围:0≤n≤2000 ,1≤k≤2000 ,链表中每个元素都满足 0≤val≤1000要求空间复杂度 O(1),时间复杂度 O(n)......
  • BM2 链表内指定区间反转
    描述将一个节点数为size链表m 位置到 n位置之间的区间反转,要求时间复杂度 O(n),空间复杂度 O(1)。例如:给出的链表为 1→2→3→4→5→NULL, m=2,n=4,返回 1→4→3→2→5→NULL. 数据范围: 链表长度 0<size≤1000,0<m≤n≤size,链表中每个节点的值满足 ∣val∣≤10......
  • BM1 反转链表
    描述给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。 数据范围: 0≤n≤1000要求:空间复杂度 O(1) ,时间复杂度 O(n) 。 如当输入链表{1,2,3}时,经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。以上转......
  • python中判断多个元素是否在列表中
    判断单个元素是否在列表中时可以通过in>>>'a'in['a','b','c']True但如果是多个元素,就不能通过in进行判断此时我们可以通过集合中的issubset和issuperset方法顾名思义,issubset是判断某集合是否是另外一个集合的子集,issuperset是判断某集合是否是另外一个集合的超集>>>......
  • LeetCode 24. 两两交换链表中的节点
    题目链接:LeetCode24.两两交换链表中的节点本题不涉及算法,直接模拟就可以了,但是模拟的过程中,最好进行画图演示,不然容易出错。想要达到两两交换链表中节点的效果,就需要按照以下三个步骤进行。同时为了将头结点和非头结点统一处理,因此新建一个虚拟头结点,初始时,cur指向虚拟头结......
  • 合并k个已排序的链表
    描述合并k 个升序的链表并将结果作为一个升序的链表返回其头节点。 数据范围:节点总数 0≤n≤5000,每个节点的val满足∣val∣<=1000要求:时间复杂度 O(nlogn) 示例输入:[{1,2},{1,4,5},{6}]返回值:{1,1,2,4,5,6} 算法思想1、将k个链表两两进行合并(采用顺......
  • 逻辑判断
    >>>1or21>>>-1or3-1>>>0or-1-1>>>0or100100>>>''or1010>>>'s'or0's'>>>'a'or'b''a'>>>4and8......
  • Element el-table 判断是否有滚动条
    判断是否有滚动条//dom元素constdom=this.$refs.uploadTableRef?.bodyWrapper//滚动到底部if(num>7&&dom?.scrollTop+dom?.clientHeight===dom?.scrollHeight){console.log(2)//元素滚动条滚动this.$refs.uploadTableRef?.bodyWrapper?.scrollTo(0,......