141. 环形链表 - 力扣（LeetCode）

发布：2021年8月1日20:49:51

问题描述及示例

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

	输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

	输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

	输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/linked-list-cycle	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个有效索引。

我的题解

我的题解1（容易招打的解法）

em……，看到题目的第一反应就是用数组变量visited来存储各个节点的访问情况（true表示访问过，false表示未访问过），如果当前访问节点的next域指向的节点的访问情况为true则说明链表中存在环路。用一个p指针来指向当前访问节点，先将当前节点的访问情况置为true，在判断其next域所指向的节点是否被访问过。当然，由于p被初始化为head.next，所以要在while循环外先对head首元节点做判断。然后，

在写下面这个程序的思路总结时，我突然发现，其实可以不用特意设置一个p指针，改进后的做法看下面的第二个程序。

其实下面的这个程序的解法会碰到visited数组中的元素与节点不方便对应的问题，所以我才想到通过给每个节点对象添加used属性来对节点的的访问情况做一个标记。既然有了这种方法，那visited数组自然也用不到了，p指针也可以省略了，因为不用特意处理首元节点了。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
  if(head && head.next) {
    head.used = true;
  } else {
    return false;
  }
  let p = head.next;
  while(p) {
    p.used = true;
    if(!p.next) {
      return false;
    }
    if(p.next.used) {
      return true;
    }
    p = p.next;
  }
};

提交记录
20 / 20 个通过测试用例
状态：通过
执行用时：88 ms, 在所有 JavaScript 提交中击败了71.89%的用户
内存消耗：40.5 MB, 在所有 JavaScript 提交中击败了23.08%的用户
时间：2021/08/01 21:04

更新：2021年8月1日21:21:07

在写上面的思路总结的时候，我突然发现，似乎可以不用设置p指针了，也不用特意对head的首元节点做判断了。提交之后发现确实在空间和时间两方面的表现都变好了。思路和之前还是差不多的。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
  // 如果head不为空链表，或者head.next不为空，则进行访问情况的判断
  // 注意，head在程序中是始终指向当前访问节点的
  while(head) {
  	// 如果能进while循环，说明当前节点是可供访问的，先将head的访问情况置为true
    head.used = true;
    // 如果当前节点的next域为空，说明已经到达了链表尾部且此前的访问过程中没有发现环路
    // 其实该判断也可以不写，因为while循环和最后的head=head.next，可以等效完成此判断
    if(!head.next) {
      return false;
    }
    // 如果当前节点不是链尾，则检查当前节点的next域指向的节点是否已经被访问过，
    // 如果已被访问过，则说明链表中存在环路
    if(head.next.used) {
      return true;
    }
    // 如果经过上面检查没有环路，则继续访问下一个节点
    head = head.next;
  }
  // 如果传入一个空链表，则直接返回false；
  // 如果上面那个if(!head.next)判断不写，这里也充当了对是否到达队尾的判断
  return false;
};

提交记录
20 / 20 个通过测试用例
状态：通过
执行用时：80 ms, 在所有 JavaScript 提交中击败了87.25%的用户
内存消耗：39.8 MB, 在所有 JavaScript 提交中击败了97.84%的用户
时间：2021/08/01 21:20