[路飞]_leetcode-142-环形链表 II

「这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战」

[题目地址][B站地址]

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

示例 1：

输入： head = [3,2,0,-4], pos = 1
输出： 返回索引为 1 的链表节点
解释： 链表中有一个环，其尾部连接到第二个节点。
复制代码

示例 2：

输入： head = [1,2], pos = 0
输出： 返回索引为 0 的链表节点
解释： 链表中有一个环，其尾部连接到第一个节点。
复制代码

示例 3：

输入： head = [1], pos = -1
输出： 返回 null
解释： 链表中没有环。
复制代码

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

进阶： 你是否可以使用 O(1) 空间解决此题？

这个题很简答哈，解题思路如下：

1. 首先需要特判链表为空的情况，如果链表为空，返回 null
2. 遍历链表，如果当前节点没有标记，则加上标记，标记该节点遍历过
3. 如果链表没有环，则整个遍历会走到链表末尾，返回 null 即可
4. 如果链表有环，则会出现遍历到一个节点，该节点已经有了标记的情况，该节点就是入环的第一个节点，返回该节点即可

整体过程如下：

代码如下：

var detectCycle = function(head) {
  // 如果是空链表，肯定没有环，返回 null
  if(head === null) return null;
  // 遍历链表
  while(head){
    // 如果该链表已经遍历过，返回该节点
    if(head.tag) return head;
    // 否则给节点加上标记
    head.tag = 'been'
    head = head.next;
  }
  // 如果遍历走到了链表末尾，返回 null
  return null;
};
复制代码

至此我们就完成了 leetcode-142-环形链表 II

如有任何问题或建议，欢迎留言讨论！