c++中如何找到链表环的入口_c++链表环入口查找方法-C++-PHP中文网

c++中如何找到链表环的入口_c++链表环入口查找方法

穿越時空

发布： 2025-10-07 17:02:01

原创

752人浏览过

使用快慢指针可判断链表是否有环并找到入口点。首先，slow和fast指针从头节点出发，slow每次走一步，fast走两步；若fast与slow相遇，则存在环。接着，将slow重置为头节点，两指针同步前进，再次相遇处即为环入口。原理在于：设头到入口距离为a，相遇点距入口为b，环剩余为c，由2(a+b)=a+2b+c得a=c，故从头和相遇点同时出发会于入口相遇。C++实现中，先通过循环判断是否相遇，无环则返回nullptr；有环则重定位slow至头节点，两指针同速前行直至相遇，返回该节点。此法时间复杂度O(n)，空间复杂度O(1)，适用于面试高频考点。

c++中如何找到链表环的入口_c++链表环入口查找方法

在C++中判断链表是否有环，并找到环的入口点，通常使用快慢指针（Floyd判圈法）。这种方法高效且不需要额外存储空间，时间复杂度为O(n)，空间复杂度为O(1)。

1. 判断链表是否存在环

使用两个指针，一个慢指针每次前进一步，一个快指针每次前进两步。如果链表存在环，快指针最终会追上慢指针。

步骤：

初始化两个指针：slow 和 fast，都指向头节点。
循环移动：slow = slow->next，fast = fast->next->next。
如果 fast == slow，说明有环；如果 fast 或 fast->next 为 nullptr，则无环。

2. 找到环的入口节点

当快慢指针相遇后，将其中一个指针重新指向头节点，然后两个指针都以每次一步的速度前进。它们再次相遇的位置就是环的入口。

立即学习“C++免费学习笔记（深入）”；

Text-To-Pokemon口袋妖怪

输入文本生成自己的Pokemon，还有各种选项来定制自己的口袋妖怪

查看详情

原理简述：

设从头到环入口距离为 a，环入口到相遇点为 b，环剩余部分为 c。
慢指针走了 a + b 步，快指针走了 a + b + c + b = a + 2b + c。
因为快指针速度是慢指针的两倍：2(a + b) = a + 2b + c → a = c。
所以从头节点和相遇点同时出发，一步一走，会在入口相遇。

3. C++ 实现代码

以下是一个完整的示例实现：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
<p>ListNode<em> detectCycle(ListNode</em> head) {
if (!head || !head->next) return nullptr;</p><pre class='brush:php;toolbar:false;'>ListNode* slow = head;
ListNode* fast = head;

// 第一步：找相遇点
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) break;
}

// 如果没有相遇，说明无环
if (!fast || !fast->next) return nullptr;

// 第二步：找环入口
slow = head;
while (slow != fast) {
    slow = slow->next;
    fast = fast->next;
}

return slow; // 返回环入口节点

登录后复制

}

基本上就这些。只要理解快慢指针的运行规律和数学推导，就能轻松定位环的入口。这个方法在面试中非常常见，建议熟练掌握。

以上就是c++++中如何找到链表环的入口_c++链表环入口查找方法的详细内容，更多请关注php中文网其它相关文章！