给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
参考代码
总结:
- 了解了java中的几种像hashSet,Stack等结构
- 开始自己想的是集合法,并且类型指定为Integer即可,不占内存嘛,
但是发现如果有相同的数但又不存在环怎么办,所以最后只能使用节点来判断 - 第一种方法很巧妙其实就有点像高中物理的追击问题,但是最开始
p2.next != null
一直没有想明白,最后画图发现了代码中的解释,所以一定要多动笔多画,把自己当做是解决问题的机器,解决问题 - 观阴阳之开阖以名命物,知存亡之门户,筹策万类之始终,达人心之理,变化之朕焉,而守司其门户。故圣人之在天下也,自古及今,其道一也。变化无穷,各有所归,或陰或陽,或柔或刚,或开或闭,或驰或张。
参考代码
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
HashSet<ListNode> hashSet = new HashSet<>();
while (head != null) {
if (hashSet.contains(head)) {
return true;
}
hashSet.add(head);
head = head.next;
}
return false;
}
2021年9月19日
题目来源力扣链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnwzei/
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)