LeetCode141-环形链表检测
2024-10-19 02:15:20
题目
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
其实就是检测一个链表是不是唤醒链表,是的话返回true否则返回false。
快慢指针实现,快指针一次走两步,慢指针一次走一步。
如果是环形链表,两个指针最后一定可以相遇,如果不是的话就无法相遇,返回false。时间复杂度是O(n),空间复杂度是O(1)。
第二种思路可以将链表中走过的节点都保存到hash表中,最后如果有重复的元素就代表是环形链表。
代码实现
/**
* 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(head==null){
return false;
}
ListNode first = head;
ListNode second = head.next;
while(second!=null&&second.next!=null){
if(first==second){
return true;
}
first = first.next;
second = second.next.next;
}
return false;
}
}
最新文章
- 数据结构与算法 Big O 备忘录与现实
- table首行固定
- 【学】ECMA6的新特性1
- fastReport 运行时设计报表 (mtm)
- SecureCRT控制台显示中文字符的设置
- Spring Cloud Eureka Server例子程序
- html网页代码各种名称及作用
- python中telnetlib模块的使用
- maven构建SSM--pox.mxl
- SignalR简单Demo
- C# T4 模板 数据库实体类生成模板(带注释,娱乐用)
- JarvisOJ BASIC -.-字符串
- Cent os 6.8添加中文字体
- QT+VS2013 1配置和安装
- 4、css盒模型和文本溢出
- adb 获取包名
- elasticsearch简介和倒排序索引介绍
- MySql数据库恢复(*frm)文件
- Jquery 获取Checkbox值,prop 和 attr 函数区别
- GitHub Desktop使用