判断⼀个链表是否有环的⼏种⽅法
⼀、单链表是否有环
思路分析：
单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某⼀个节点，这样在链表的尾部形成⼀个环形结构。判断链表是否有环，有以下⼏种⽅法。
1// 链表的节点结构如下
2 typedef struct node
3 {
4int data;
5struct node *next;
6 } NODE;
（1）最常⽤⽅法：定义两个指针，同时从链表的头节点出发，⼀个指针⼀次⾛⼀步，另⼀个指针⼀次⾛两步。如果⾛得快的指针追上了⾛得慢的指针，那么链表就是环形链表；如果⾛得快的指针⾛到了链表的末尾（next指向 NULL 1// 判断链表是否有环
2bool IsLoop(NODE *head) // 假设为带头节点的单链表
3 {
4if (head == NULL)
5return false;
6
7 NODE *slow = head->next; // 初始时，慢指针从头节点开始⾛1步
8if (slow == NULL)
9return false;
10
11 NODE *fast = slow->next; // 初始时，快指针从头节点开始⾛2步
12while (fast != NULL && slow != NULL) // 当单链表没有环时，循环到链表尾结束
13 {
14if (fast == slow)
15return true;
16
17 slow = slow->next; // 慢指针每次⾛⼀步
18
19 fast = fast->next;
20if (fast != NULL)
21 fast = fast->next;
22 }
23
24return false;
25 }
（2）通过使⽤STL库中的map表进⾏映射。⾸先定义map<NODE *, int> m；将⼀个 NODE * 指针映射成数组的下标，并赋值为⼀个 int 类型的数值。然后从链表的头指针开始往后遍
历，每次遇到⼀个指针p，就判断 m[p] 是否为0。如果为0，则将m[p]赋值为1，表⽰该节点第⼀次访问；⽽如果m[p]的值为1，则说明这个节点已经被访问过⼀次了，于是就形成
了环。
1 #include <iostream>
2using namespace std;
3 #include <map>
4
5// 使⽤STL中的map来判断单链表中是否有环
6 map<NODE *, int> m;
数组和链表7bool IsLoop_2(NODE *head)
8 {
9if (head == NULL)
10return false;
11
12 NODE *p = head;
13
14while (p)
15 {
16if (m[p] == 0) // ⼀般默认值都是0
17 m[p] = 1;
18else if (m[p] == 1)
19return true;
20
21 p = p->next;
22 }
23
24return false;
25 }
（3）不推荐使⽤：定义⼀个指针数组，初始化为空指针，从链表的头指针开始往后遍历，每次遇到⼀个指针就跟指针数组中的指针相⽐较，若没有到相同的指针，说明这个
节点是第⼀次访问，还没有形成环，将这个指针添加到指针数组中去。若在指针数组中到了同样的指针，说明这个节点已经访问过了，于是就形成了环。
⼆、若单链表有环，如何出环的⼊⼝节点。
步骤：
<1> 定义两个指针p1和p2，在初始化时都指向链表的头节点。
<2> 如果链表中的环有n个节点，指针p1先在链表上向前移动n步。
<3> 然后指针p1和p2以相同的速度在链表上向前移动直到它们相遇。
<4> 它们相遇的节点就是环的⼊⼝节点。
那么如何得到环中的节点数⽬？
可使⽤上述⽅法（1），即通过⼀快⼀慢两个指针来解决这个问题。当两个指针相遇时，表明链表中存
在环。两个指针相遇的节点⼀定是在环中。可以从这个节点出发，⼀边继
续向前移动⼀边计数，当再次回到这个节点时，即可得到环中的节点数了。
1// 1、先求出环中的任⼀节点
2 NODE *MeetingNode(NODE *head) // 假设为带头节点的单链表
3 {
4if (head == NULL)
5return NULL;
6
7 NODE *slow = head->next; // 初始时，慢指针从头节点开始⾛1步
8if (slow == NULL)
9return NULL;
10
11 NODE *fast = slow->next; // 初始时，快指针从头节点开始⾛2步
12while (fast != NULL && slow != NULL) // 当单链表没有环时，循环到链表尾结束
13 {
14if (fast == slow)
15return fast;
16
17 slow = slow->next; // 慢指针每次⾛⼀步
18
19 fast = fast->next;
20if (fast != NULL)
21 fast = fast->next;
22 }
23
24return NULL;
25 }
26
27// 2、从已到的那个环中节点出发，⼀边继续向前移动，⼀边计数，当再次回到这个节点时，就可得到环中的节点数了。
28 NODE *EntryNodeOfLoop(NODE *head)
29 {
30 NODE *meetingNode = MeetingNode(head); // 先出环中的任⼀节点
31if (meetingNode == NULL)
32return NULL;
33
34int count = 1; // 计算环中的节点数
35 NODE *p = meetingNode;
36while (p != meetingNode)
37 {
38 p = p->next;
39 ++count;
40 }
41
42 p = head;
43for (int i = 0; i < count; i++) // 让p从头节点开始，先在链表上向前移动count步
44 p = p->next;
45
46 NODE *q = head; // q从头节点开始
47while (q != p) // p和q以相同的速度向前移动，当q指向环的⼊⼝节点时，p已经围绕着环⾛了⼀圈⼜回到了⼊⼝节点。
48 {
49 q = q->next;
50 p = p->next;
51 }
52
53return p;
54 }
备注：在MeetingNode⽅法中，当快慢指针（slow、fast）相遇时，slow指针肯定没有遍历完链表，⽽fast指针已经在环内循环了n（n>=1）圈。假设slow指针⾛了s步，则fast指针⾛了2s步。同时，fast指针的步数还等于s加上在环上多转的n圈，设环长为r，则满⾜如下关系表达式：
2s = s + nr;
所以可知：s = nr;
假设链表的头节点到“环的尾节点“的长度为L（注意，L不⼀定是链表长度），环的⼊⼝节点与相遇点的距离为x，链表的头节点到环⼊⼝的距离为a，则满⾜如下关系表达式：
a + x = s = nr;
可得：a + x = (n - 1)r + r = (n - 1)r + (L - a)
进⼀步得：a = (n - 1)r + (L -a - x)
结论：
<1> (L - a -x)为相遇点到环⼊⼝节点的距离，即从相遇点开始向前移动(L -a -x)步后，会再次到达环⼊⼝节点。
<2> 从链表的头节点到环⼊⼝节点的距离＝ (n - 1) * 环内循环＋相遇点到环⼊⼝点的距离。
<3> 于是从链表头与相遇点分别设⼀个指针，每次各⾛⼀步，两个指针必定相遇，且相遇第⼀点为环⼊⼝点。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论