LeetCode 第142题：环形链表 II

题目描述

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

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

不允许修改 链表。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

示例1图片

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

示例 2：

示例2图片

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

示例 3：

示例3图片

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

提示

链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引

解题思路

方法一：快慢指针（Floyd 判圈算法）

这是一个经典的算法问题，可以使用 Floyd 判圈算法（也称为龟兔赛跑算法）来解决。算法分为两个阶段：

判断是否存在环
如果存在环，找到环的入口

关键点：

使用快慢指针判断是否有环
利用数学关系找到环的入口
理解快慢指针相遇时的位置特性

具体步骤：

设置两个指针，快指针和慢指针，初始都指向头节点
快指针每次走两步，慢指针每次走一步，直到它们相遇或快指针到达链表末尾
如果快指针到达末尾，说明无环，返回null
如果两指针相遇，将其中一个指针重新指向头节点，然后两个指针每次都走一步
当两个指针再次相遇时，相遇点就是环的入口

数学证明：

设链表头到环入口的距离为a，环入口到相遇点的距离为b，相遇点到环入口的距离为c
当快慢指针相遇时：
- 慢指针走过的距离：a + b
- 快指针走过的距离：a + b + n(b + c)，其中n是快指针在环内走的圈数
- 由于快指针速度是慢指针的两倍，所以：2(a + b) = a + b + n(b + c)
- 化简得：a = (n-1)(b + c) + c
- 这意味着从头节点到环入口的距离等于从相遇点继续走到环入口的距离

时间复杂度：O(n)，其中 n 是链表中节点的数目。空间复杂度：O(1)，只需要两个指针。

方法二：哈希表

使用哈希表记录访问过的节点，第一个重复访问的节点就是环的入口。

关键点：

使用哈希表存储访问过的节点
遍历链表直到找到重复节点或到达末尾

具体步骤：

创建一个哈希表用于存储访问过的节点
遍历链表，对于每个节点：
- 如果当前节点已在哈希表中，则该节点就是环的入口
- 否则将当前节点加入哈希表
如果遍历结束都没有找到重复节点，则无环，返回null

时间复杂度：O(n)，其中 n 是链表中节点的数目。空间复杂度：O(n)，需要哈希表存储访问过的节点。

图解思路

Floyd算法分析

以示例1为例：head = [3,2,0,-4], pos = 1

第一阶段（判断是否有环）：

步骤	慢指针	快指针	说明
初始状态	3	3	同时指向头节点
第1步	2	0	慢走一步，快走两步
第2步	0	2	继续移动
第3步	-4	0	继续移动
第4步	2	-4	继续移动
第5步	0	2	相遇点在0

第二阶段（找环入口）：

步骤	指针1（从头开始）	指针2（从相遇点开始）	说明
初始状态	3	0	重置指针1到头节点
第1步	2	-4	同时走一步
第2步	2	2	在环入口相遇

代码实现

C# 实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode DetectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        
        // 第一阶段：使用快慢指针找到相遇点
        ListNode slow = head;
        ListNode fast = head;
        bool hasCycle = false;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        
        // 如果没有环，返回null
        if (!hasCycle) {
            return null;
        }
        
        // 第二阶段：找到环的入口
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
}

Python 实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None
        
        # 第一阶段：使用快慢指针找到相遇点
        slow = fast = head
        has_cycle = False
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                has_cycle = True
                break
        
        # 如果没有环，返回None
        if not has_cycle:
            return None
        
        # 第二阶段：找到环的入口
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        return slow

C++ 实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) {
            return nullptr;
        }
        
        // 第一阶段：使用快慢指针找到相遇点
        ListNode *slow = head;
        ListNode *fast = head;
        bool hasCycle = false;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        
        // 如果没有环，返回nullptr
        if (!hasCycle) {
            return nullptr;
        }
        
        // 第二阶段：找到环的入口
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        
        return slow;
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	88 ms	40.2 MB	实现简洁，性能良好
Python	52 ms	17.8 MB	代码最简洁
C++	8 ms	7.5 MB	性能最优，内存占用最小