地方门户网站赚钱吗,河北省最新任免,做qq空间动态皮肤网站,福千欣隆网站建设公司怎么样操作系统#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言#xff1a;C11
题目描述#xff1a;
给一个链表#xff0c;如果有环#xff0c;请找出该链表的入环节点#xff1b;如果没有环#xff0c;则返回 null。你不能修改链表本身。 示例#xff1a;
输入… 操作系统ubuntu22.04 IDE:Visual Studio Code 编程语言C11
题目描述
给一个链表如果有环请找出该链表的入环节点如果没有环则返回 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 iostreamint 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;
}运行结果
环的入口节点值为2
