当前位置：首页 > ai >正文

C++面试(8)-----求链表中环的入口节点

ai 2025/6/19 6:24:19

操作系统：ubuntu22.04
IDE:Visual Studio Code
编程语言：C++11

题目描述：

给一个链表，如果有环，请找出该链表的入环节点；如果没有环，则返回 null。

你不能修改链表本身。
示例：

输入链表: 3 -> 2 -> 0 -> -4↖        ↗\______/
环的入口是节点 2。

解题思路（经典双指针法）

判断链表是否有环，并找出环的入口节点，是一个非常经典的算法问题。我们可以使用快慢指针 + 数学推导的方法来解决。
步骤详解：

第一步：判断是否有环（快慢指针）
- 定义两个指针 slow 和 fast，都从头节点出发；
- slow 每次走一步，fast 每次走两步；
- 如果链表有环，两个指针一定会相遇；
- 如果 fast 或 fast->next 为 nullptr，说明无环。
第二步：找到环的入口节点
假设：
- 头节点到环入口的距离为 a；
- 环入口到相遇点的距离为 b；
- 相遇点绕回环入口的距离为 c。

通过数学推导可以得出：

当第一次相遇时，让 fast 回到头节点，并且每次只走一步；
再次相遇的位置就是环的入口。

实现代码

// 定义链表节点结构体
struct ListNode {int val;ListNode* next;ListNode( int x ) : val( x ), next( nullptr ) {}
};class Solution {
public:// 函数功能：查找链表中环的入口节点ListNode* detectCycle( ListNode* head ){// 如果头节点为空，直接返回 nullif ( head == nullptr )return nullptr;// 定义快慢指针ListNode* slow = head;ListNode* fast = head;// 第一次遍历：判断是否有环while ( fast != nullptr && fast->next != nullptr ){slow = slow->next;        // 慢指针每次走一步fast = fast->next->next;  // 快指针每次走两步// 如果相遇，说明有环if ( slow == fast ){// 第二次遍历：找环的入口fast = head;  // 快指针回到头节点while ( fast != slow ){fast = fast->next;slow = slow->next;}return fast;  // 返回环的入口节点}}// 如果没相遇，说明没有环return nullptr;}
};#include <iostream>int main()
{// 构建测试链表：3 -> 2 -> 0 -> -4 -> 2（形成环）ListNode* node1 = new ListNode( 3 );ListNode* node2 = new ListNode( 2 );ListNode* node3 = new ListNode( 0 );ListNode* node4 = new ListNode( -4 );node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node2;  // 形成环Solution sol;ListNode* entryNode = sol.detectCycle( node1 );if ( entryNode != nullptr ){std::cout << "环的入口节点值为：" << entryNode->val << std::endl;}else{std::cout << "该链表没有环。" << std::endl;}return 0;
}