力扣（LeetCode）环形链表 个人题解
2024-09-01 17:05:07
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
一开始题意理解错了，都输入了pos还判断环形做什么，后来明白了，pos并不是直接给出的。
那么做法就清晰起来了。快慢指针的思路。快指针永远比慢指针快一步。
假设没有环形，快指针走到末尾就结束了。
假设有环形，快指针到末尾后又回到了循环中，虽然此时慢指针的位置并不固定，但是因为快指针永远比慢指针快一步，所以在经过若干个循环后，两个指针必定会相遇，也就表示有环形。
这里的代码和官方题解略有不同，使用了哑节点来避开空链表报错的陷阱。
代码如下：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode fast = head;
ListNode slow = dummyHead;
while (fast != slow) {
if (fast == null || fast.next == null)
return false;
fast = fast.next.next;
slow = slow.next;
}
return true;
}
}
最新文章
- RAC 主库配置单实例ADG
- virtualbox之usb设备的分配
- IOS 其它语言比较-Objc与JAVA的比较
- OpenStack 企业私有云的若干需求（9）: 云管理平台 CMP
- zookeeper源码分析二FASTLEADER选举算法
- ASP.NET MVC4 部分视图
- 利用.htaccess绑定子域名到子目录（亲测万网可用）
- AIX 第4章 指令记录
- COM 学习小记录
- Eclipse中查看Android模拟器SD卡目录
- 转载：js 创建对象、属性、方法
- zoj 3656 2-sat 不错的题
- struts2+ajax实现异步验证实现
- jetty compile
- WPF 杂谈——资源文件
- [转]同一台Windows机器中启动多个Memcached服务
- iOS开发之三：常用控件--UILabel的使用
- Python random模块方法
- 事件委托在ios下面失效
- js根据鼠标和键盘判断页面是否长时间未进行操作