链表 141. 环形链表

总结：

①最基础的方法：双指针循环（性能差）
②投机法：Json.stringify(head)，利用该序列化方法自带的「有互相引用就报错」
③给链表加个 tag【最优】：给每个节点加标记
④利用 set 作为哈希表

function circleTag3(head) {
    while(head) {
        if(head.tag) {
            return true;
        }
        head.tag = true;
        head = head.next;
    }
    return false
}
function circleHash4(head) {
    let set = new WeakSet();
    while(head) {
        if(set.has(head)) {
            return true;
        }
        set.add(head);
        head = head.next;
    }
    return false
}

力扣 141. 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

进阶：

你能用 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
}

// 两个指针，但是性能太差
var hasCycle = function (head) {
    let cursor1 = head;
    let cursor2 = head.next;
    if (!cursor1 || !cursor2) { return false }
    while (cursor1) {
        while (cursor2) {
            if (cursor2.value === cursor1.value) {
                return true
            }
            cursor2 = cursor2.next;
        }
        cursor1 = cursor1.next;
    }
    return false
};

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
}

链表 141. 环形链表

链表 141. 环形链表

力扣 141. 环形链表

CATALOG

FEATURED TAGS

FRIENDS