环形链表问题的探究与代码实现

在数据结构与算法的学习中，环形链表是一个经典的问题。它不仅考察对链表这种数据结构的理解，还涉及到指针操作和逻辑推理。本文将结合代码和图文，深入分析如何判断链表中是否有环以及如何找到环的入口点。
 

目录

一、判断链表中是否有环 

​编辑代码实现（C语言）

 

二、找到环形链表的入口点 ​编辑

思路一 

代码实现（C语言） 

思路二：转换为找链表交点 

代码实现（C语言） 

三、总结 

---

仓库 https://blog.csdn.net/nplplus/category_12904039.html

作者主页  共享家9527-CSDN博客

一、判断链表中是否有环
 

判断链表中是否存在环，常用的方法是快慢指针法。
 
思路
 
定义两个指针，慢指针（slow）每次移动一个节点，快指针（fast）每次移动两个节点。如果链表中存在环，那么快指针最终一定会追上慢指针；如果不存在环，快指针会先到达链表末尾。
 

错误思想

代码实现（C语言）

 

cbool hasCycle(struct ListNode *head) {struct ListNode* slow, *fast;slow = fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;if (slow == fast)return true;}return false;
}

分析
 

在上述代码中，初始化快慢指针都指向链表头节点。在循环中，不断移动快慢指针。当快慢指针相遇时，说明链表存在环，返回 true ；如果循环结束，快指针到达链表末尾，说明链表无环，返回 false 。
 

二、找到环形链表的入口点
 

找到环形链表的入口点同样可以使用快慢指针法，并且在找到相遇点后，通过数学推导得出结论来找到入口点。同时，还可以将找入口点的问题巧妙地转换成找链表交点的问题，以下为您详细介绍两种思路。
 

思路一
 

首先使用快慢指针找到相遇点。
 
假设起始点到入口点距离为 L ，入口点到相遇点距离为 X ，环的长度为 C 。当快慢指针相遇时，慢指针走过的距离为 L + X ，快指针走过的距离为 L + n*C + X （ n 为快指针在环中绕的圈数），且快指针走过的距离是慢指针的2倍，即 2*(L + X) = L + n*C + X ，化简可得 L = n*C - X 。
 
从结论可以看出，一个指针从相遇点走，一个指针从起始点走，它们会在入口点相遇。
 

代码实现（C语言）
 

cstruct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast, *slow;fast = slow = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;if (slow == fast) {struct ListNode* meet = slow;struct ListNode* start = head;while (meet != start) {meet = meet->next;start = start->next;}return meet;}}return NULL;
}

 
 

---

思路二：转换为找链表交点
 

图片中的代码展示了将找环形链表入口点转换为找链表交点的方法。当快慢指针相遇后：
 
定义 meet 指针指向相遇点，此时 struct ListNode* meet = slow;  。
 
定义 lt1 指针从相遇点的下一个节点开始，即 struct ListNode* lt1 = meet->next;  。
 
定义 lt2 指针指向链表头节点，即 struct ListNode* lt2 = head;  。
 
将相遇点的next指针置为 NULL ，即 meet->next = NULL;  ，这样就把原环形链表处理成了两个普通链表。
 
最后通过调用 getIntersectionNode(lt1, lt2) 函数来获取这两个链表的交点，该交点就是原环形链表的入口点。
 

代码实现（C语言）
 

cstruct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast, *slow;fast = slow = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;if (slow == fast) {// 转换成lt1和lt2求交点struct ListNode* meet = slow;struct ListNode* lt1 = meet->next;struct ListNode* lt2 = head;meet->next = NULL;return getIntersectionNode(lt1, lt2);}}return NULL;
}

 
 
分析
 
通过这两种方法，都能有效地找到环形链表的入口点。第一种方法基于数学推导，利用相遇点和起始点到入口点的关系；第二种方法则通过巧妙地转换问题，将找环形链表入口点变为找两个普通链表的交点。无论哪种方法，都体现了算法设计中利用已有结论和转换思路来解决问题的技巧。在实际应用中，类似的思路也可以用于解决一些与循环、追踪路径相关的问题。
 

三、总结
 

环形链表问题是算法学习中的一个重要知识点。通过快慢指针法，我们可以高效地判断链表是否有环以及找到环的入口点。理解这个问题不仅有助于加深对链表数据结构的认识，还能提升逻辑思维和算法设计能力。在实际应用中，类似的思路也可以用于解决一些与循环、追踪路径相关的问题。