链表 141. 环形链表
力扣 141. 环形链表
给定一个链表，判断链表中是否有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
- 1、自己的算法：非常耗费内存，导致力扣不给我过…
但是我跑了报错的测试用例…只要内存够…我的算法返回的结果是正确的
var hasCycle = function(head) {
if (head === null || head.next === null) {
return false;
}
let circle = false;
// 用两个数组存储当前节点和下一个节点的值
let arr = [head.val];
let arrNext = [head.next.val];
// 遍历链表每一项，判断是否和之前的节点相同
for(let i = head.next; i.next !== null && !circle; i = i.next) {
// 在 arr 存在且 arr 和 arrNext 的下标相等
if (arr.includes(i.val) && (arr.indexOf(i.val) === arrNext.indexOf(i.next.val))) {
circle = true;
return circle;
}
arr.push(i.val);
arrNext.push(i.next.val);
}
return circle
}
- 2、我觉得有点神奇的/投机的方法
时间复杂度：O(n)，空间复杂度：xx
【查了下JSON.stringify()原理也是要遍历参数进行处理的】
// 除非不报错，报错就是有环
var hasCycle = (head) => {
try {
JSON.stringify(head);
} catch (error) {
return true
}
return false
}
补充： JSON.stringify()方法对循环引用本身就会报错，截图来源于 MDN
- 3、我觉得还不错的算法
时间复杂度：O(n)，空间复杂度：xx
var hasCycle = (head) => {
while (head !== null) {
// 出现已经标记过的节点就代表有重复节点，存在环
if(head.tag) {
return true
}
// 给每一个节点打标记
head.tag = true;
head = head.next;
}
return false
}
- 4、按照官方提示，哈希表的思维算法
var hasCycle = (head) => {
// Set中的元素只会出现一次
let set = new Set();
while(head !== null){
// 判断是否存在过
if(set.has(head)) {
return true;
}
// 添加到 set 中
set.add(head);
head = head.next;
}
return false
}