算法：给定一个链表，判断链表中是否存在环

### 知识点详解 #### 一、链表的基本概念 **链表**是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据域和指向下一个节点的指针域。链表根据节点间连接关系的不同，可以分为单向链表、双向链表和循环链表。 1. **单向链表**：每个节点只包含一个指向其后继节点的指针。 2. **双向链表**：每个节点包含两个指针，一个指向前驱节点，另一个指向后继节点。 3. **循环链表**：单向或双向链表的一种变种，在这种链表中，最后一个节点的指针指向链表的第一个节点，形成一个环状结构。 #### 二、链表中的环问题 在链表中，如果某个节点的指针不是指向`NULL`，而是指向了链表中的某个节点，则称该链表中存在环。检测链表中是否存在环是链表操作中一个常见的问题。 #### 三、快慢指针算法 快慢指针算法是一种用于检测链表中是否存在环的有效方法，也称为“龟兔赛跑”算法。这种方法使用两个指针，一个快指针（每次移动两步），一个慢指针（每次移动一步）。 - **初始化**：将快慢指针都指向链表头结点。 - **遍历过程**： - 慢指针每次移动一步； - 快指针每次移动两步； - 如果链表中存在环，则快指针最终会追上慢指针； - 如果链表中不存在环，则快指针会先到达链表的尾部。 - **退出条件**： - 当快指针或快指针的下一个节点为`NULL`时，说明链表无环； - 当快指针与慢指针相遇时，说明链表有环。 #### 四、多种编程语言实现 针对题目要求，我们可以用Python、Java和C语言实现快慢指针算法来检测链表中是否存在环。 ##### 1. Python 实现 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def has_cycle(head): if not head: return False slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False ``` ##### 2. Java 实现 ```java class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; this.next = null; } } public class HasCycle { public static boolean hasCycle(ListNode head) { if (head == null) { return false; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; } public static void main(String[] args) { // 构建一个有环的链表用于测试 ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node2; // 形成环 System.out.println(hasCycle(node1)); } } ``` ##### 3. C 语言实现 ```c #include <stdio.h> #include <stdbool.h> // 链表节点结构体 typedef struct ListNode { int val; struct ListNode *next; } ListNode; bool hasCycle(ListNode *head) { if (head == NULL) { return false; } ListNode *slow = head; ListNode *fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return true; } } return false; } ``` 以上三种实现方式均遵循了快慢指针算法的基本逻辑，并且分别适用于不同的编程环境。通过这些实现，我们可以有效地检测链表中是否存在环。