141.环形链表

发表于 2021-09-15 分类于 LeetCode题库阅读次数：

给你一个链表的头节点 head ，判断链表中是否有环。

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

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3：

1
2
3

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

解题思路

这是一道经典的双指针题目，使用快慢指针检测环形链表。

核心思想

使用两个指针，一个快指针，一个慢指针
快指针每次移动两步，慢指针每次移动一步
如果存在环，快指针最终会追上慢指针

方法一：快慢指针（推荐）

时间复杂度 O(n)、空间复杂度 O(1)

/**
 * 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) {
        return false;
    }
    
    let slow = head;
    let fast = head.next;
    
    while (slow !== fast) {
        // 如果快指针到达末尾，说明没有环
        if (!fast || !fast.next) {
            return false;
        }
        
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return true;
};

方法二：优化版本

var hasCycle = function(head) {
    if (!head || !head.next) return false;
    
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            return true;
        }
    }
    
    return false;
};

方法三：使用Set（不符合空间要求，但思路清晰）

var hasCycle = function(head) {
    const visited = new Set();
    let current = head;
    
    while (current) {
        if (visited.has(current)) {
            return true;
        }
        visited.add(current);
        current = current.next;
    }
    
    return false;
};

方法四：标记法（破坏链表结构）

var hasCycle = function(head) {
    let current = head;
    
    while (current) {
        if (current.visited) {
            return true;
        }
        current.visited = true;
        current = current.next;
    }
    
    return false;
};

解题要点

快慢指针：
- 快指针每次移动两步
- 慢指针每次移动一步
- 如果存在环，快指针会追上慢指针
边界处理：
- 空链表：返回false
- 只有一个节点：返回false
- 快指针到达末尾：返回false
为什么快慢指针能检测环？
- 如果存在环，快指针会进入环
- 慢指针也会进入环
- 在环内，快指针每次比慢指针多走一步
- 最终快指针会追上慢指针

面试要点

高频考点：这道题是面试中的高频题目
快慢指针：考察对快慢指针的理解和应用
空间复杂度：要求O(1)空间复杂度
链表操作：考察链表的基本操作

扩展思考

为什么快慢指针能检测环？
- 在环内，快指针每次比慢指针多走一步
- 相当于快指针在追赶慢指针
- 最终会相遇
时间复杂度分析
- 快慢指针：O(n)
- Set方法：O(n)
- 空间复杂度：O(1) vs O(n)
边界情况
- 空链表：返回false
- 只有一个节点：返回false
- 没有环：快指针到达末尾
算法正确性证明
- 如果存在环，快慢指针一定会相遇
- 如果不存在环，快指针会先到达末尾
实际应用
- 检测链表是否有环
- 检测函数调用是否有循环
- 检测状态机是否有循环

最后更新: 2021-09-15

个人笔记