跳到主要内容

环形链表

· 阅读需 5 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——141题​

💡 参考代码：​

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * 判断链表中是否存在环
 * 
 * 使用Floyd判圈算法（快慢指针）:
 * - 设置两个指针，一个快指针和一个慢指针
 * - 快指针每次移动两步，慢指针每次移动一步
 * - 如果链表中存在环，快指针最终会追上慢指针
 * - 如果链表中无环，快指针会先到达链表末尾
 * 
 * 时间复杂度: O(n) - 最多遍历链表两次
 * 空间复杂度: O(1) - 只使用了两个指针的常量空间
 * 
 * @param head 链表的头节点
 * @return 如果链表中存在环则返回true，否则返回false
 */
bool hasCycle(struct ListNode *head) {
    // 处理空链表或只有一个节点的情况
    if (head == NULL || head->next == NULL) {
        return false;
    }
    
    // 初始化快慢指针
    // 慢指针指向头节点，快指针指向头节点的下一个节点
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    
    // 当快慢指针不相等时继续循环
    while (slow != fast) {
        // 如果快指针到达链表末尾，说明无环
        if (fast == NULL || fast->next == NULL) {
            return false;
        }
        
        // 移动慢指针一步，快指针两步
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 快慢指针相遇，说明存在环
    return true;
}

📖 总结：​

点击展开题目总结

🤔 环形链表

1️⃣ 题目核心信息​

🎯 功能描述：判断链表中是否存在环结构

📥 输入输出：

  • 输入：head - 链表的头节点
  • 输出：布尔值 - 存在环返回 true，否则返回 false

2️⃣ 实现原理​

💡 核心思路：使用Floyd判圈算法（快慢指针），通过两个不同速度的指针遍历链表，若存在环则快指针会追上慢指针

📋 实现步骤：

  1. 特殊情况处理：空链表或单节点链表直接返回 false
  2. 初始化快慢指针：慢指针指向头节点，快指针指向头节点的下一个节点
  3. 循环移动指针：慢指针每次移动一步，快指针每次移动两步
  4. 判断相遇：若两指针相遇则存在环，若快指针到达链表末尾则无环

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用快慢指针技巧解决环形问题
  • 巧妙利用指针速度差检测环的存在
  • 边界条件处理：提前判断空链表和单节点情况

4️⃣ 使用场景​

✅ 适用情况：​

  • 检测链表中是否存在循环引用
  • 判断数据结构是否有环状结构
  • 内存泄漏检测中的循环引用检查

⚠️ 前提条件：​

  • 链表节点结构包含 next 指针
  • 可以修改或访问链表节点的指针域

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n)，其中 n 是链表节点数，最坏情况下需要遍历整个链表
  • 💾 空间复杂度：O(1)，只使用了两个指针的常量空间

6️⃣ 注意事项​

🚩 边界情况：​

  • 空链表 (head == NULL)
  • 单节点链表 (head->next == NULL)
  • 两节点链表的环情况

💥 易错点：​

  • 快指针移动时需要检查 fast 和 fast->next 是否为 NULL
  • 指针初始化位置的选择影响循环条件
  • 循环结束条件的判断容易出错

7️⃣ 补充说明​

示例1：有环链表 [3,2,0,-4]，pos=1​

// 创建链表节点
struct ListNode n1, n2, n3, n4;
n1.val = 3;
n2.val = 2;
n3.val = 0;
n4.val = -4;

// 构建链表连接关系
n1.next = &n2;  // 3 -> 2
n2.next = &n3;  // 2 -> 0
n3.next = &n4;  // 0 -> -4
n4.next = &n2;  // -4 -> 2 (形成环，指向索引1的节点)

// 执行hasCycle(&n1)
// 初始状态: slow = &n1(3), fast = &n2(2)
// 第1轮: slow = &n2(2), fast = &n4(-4)
// 第2轮: slow = &n3(0), fast = &n3(0)  // 相遇！
// 返回 true

示例2：无环链表 [1,2]​

// 创建链表节点
struct ListNode n1, n2;
n1.val = 1;
n2.val = 2;

// 构建链表连接关系
n1.next = &n2;  // 1 -> 2
n2.next = NULL; // 2 -> NULL (无环)

// 执行hasCycle(&n1)
// 初始状态: slow = &n1(1), fast = &n2(2)
// 检查 fast->next == NULL，直接返回 false

示例3：单节点环 [1]，pos=0​

// 创建链表节点
struct ListNode n1;
n1.val = 1;
n1.next = &n1;  // 1 -> 1 (自己指向自己)

// 执行hasCycle(&n1)
// 初始状态: slow = &n1(1), fast = &n1(1)
// 开始循环前 slow == fast，直接跳出循环
// 返回 true

🎯 结构体使用方式​

// 创建一个节点
struct ListNode node1;
node1.val = 10;           // 节点存储的值是10
node1.next = NULL;        // 指向下一个节点的指针（暂时为空）

// 创建另一个节点并连接
struct ListNode node2;
node2.val = 20;
node2.next = NULL;

// 建立连接：node1指向node2
node1.next = &node2;      // &node2是node2的地址
加载评论中...