[路飞]_leetcode-141-环形链表

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

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

难度简单1244收藏分享切换为英文接收动态反馈

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

如果链表中有某个节点，可以通过连续跟踪 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
解释： 链表中没有环。
复制代码

提示：

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

解题思路1：

1. 首先特判如果 head 为空或者 head.next为空，此时肯定没有环，返回 false
2. 循环链表节点，如果当前链表节点中没有tag属性，给当前节点定义 tag 属性，标记该节点访问过，如果当前节点有 tag属性，说明我们之前访问过该节点，此时再次来到该节点，证明节点有环，返回 true
3. 如果遍历完整个链表都没有遇到有 tag 属性的节点，则证明链表没有环，返回 false

代码如下：

var hasCycle = function(head) {
    if(head === null || head.next===null) return false;
    let cur = head;
    while(cur){
        if(cur.tag) return true;
        else{
            cur.tag = 'a'
            cur = cur.next;
        }
    }
    return false;
};
复制代码

解题思路2：

1. 定义两个快慢指针 pre 和 next，初始化都指向 head
2. 当 next 不为空并且 next.next 不为空，next每次向后走一步，pre 每次向后走两步
3. 此时如果链表中有环，则 pre 和 next 会在环的起始位置相遇，返回 true。否则 遍历到链表的末尾，next或者 next.next会指向 null，返回 false

代码如下：

var hasCycle = function(head) {
    if(head === null || head.next===null) return false;
    let cur = head;
    while(cur){
        if(cur.tag) return true;
        else{
            cur.tag = 'a'
            cur = cur.next;
        }
    }
    return false;
};
复制代码

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

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