环形链表（LeetCode 141）C语言最佳解题思路

环形链表（LeetCode 141）C语言解题思路

问题描述

判断一个链表中是否存在环。

解题方法：快慢指针法

使用两个指针，一个快指针（每次移动两步），一个慢指针（每次移动一步）。如果链表中存在环，快指针最终会追上慢指针；如果不存在环，快指针会先到达链表尾部。

代码实现

#include <stdbool.h> // 链表节点结构体定义（题目自带） struct ListNode { int val; struct ListNode *next; }; // 主函数：判断链表是否有环 bool hasCycle(struct ListNode *head) { // 边界1：空链表 / 只有单个节点无后继，直接无环 if (head == NULL || head->next == NULL) { return false; } // 初始化快慢指针，起点都为头节点 struct ListNode *slow = head; struct ListNode *fast = head; // 循环条件：fast和fast->next不能为NULL（fast一次走两步，防止空指针访问） while (fast != NULL && fast->next != NULL) { slow = slow->next; // 慢：走1步 fast = fast->next->next; // 快：走2步 // 快慢指针相遇，证明存在环 if (slow == fast) { return true; } } // 循环正常退出说明fast走到链表末尾NULL，无环 return false; }

代码讲解

1. 边界条件检查

   • 如果链表为空（head == NULL）或只有一个结点（head->next == NULL），直接返回false，因为无法形成环。

2. 初始化指针

   • slow指针初始化为head，每次移动一步。
   • fast指针初始化为head->next，每次移动两步。

3. 循环检测

   • 在while循环中，判断slow和fast是否相遇。
   • 如果fast或fast->next为NULL，说明链表无环，返回false。
   • 每次循环中，slow移动一步，fast移动两步。

4. 返回结果

   • 如果slow和fast相遇，说明链表有环，返回true。

复杂度分析

• 时间复杂度：O(n)
  • 无环时，快指针最多遍历链表一次。
  • 有环时，快慢指针会在环内相遇，时间复杂度为O(n)。
• 空间复杂度：O(1)
  • 仅使用了两个指针，空间复杂度为常数。