题目
如果一个链表中包含环，如何找出环的入口节点？例如，在下图中的链表中，环的入口节点是节点3。
分析
将这个问题解剖开。分为俩步
- 判断是否有环
- 有环再找入口节点
第一个问题：我们用快慢指针来判断，只要相遇就有环，快指针走到头就是没有环。
第二个问题：与剑指Offer - 面试题22：链表中倒数第K个节点第二种方法思想相似，可以先去看看这个题。我们先定义链表头到入口距离m，环的长度为n。那么可以先让快指针从头开始走环的长度n，那么快指针走到环的入口还需要走m长度。刚好此时慢指针也一起走，走到入口处相遇。比较绕建议自己画一画。
整理一下：快指针需要走m+n的长度，慢指针需要走m长度，所以让快指针先走n长度，然后快慢同时走相遇就是入口处。
在代码中我们构造了一个与上图相同的链表。
C++
#include <iostream> using namespace std; typedef int TElemType;//链表节点值的数据类型 struct ListNode { TElemType Data; struct ListNode* Next; }; ListNode* CreateList(int data)//创建节点 { ListNode* node = new ListNode(); node->Data = data; node->Next = nullptr; return node; } void connect(ListNode* front, ListNode* rear)//连接节点 { front->Next = rear; } ListNode* EntranceNode(ListNode* pHead)//查找环入口 { if (nullptr == pHead) { return nullptr; } ListNode* fast = pHead;//快指针 ListNode* slow = pHead;//慢指针 bool sign = false;//默认无环 //判断有无环 while (fast->Next != nullptr && sign == false) { fast = fast->Next->Next; slow = slow->Next; if (fast == slow) { sign = true; } } if (sign == false)//无环 { return nullptr; } //计算环长 int len = 0; do { fast = fast->Next; len++; } while (fast != slow); //复原指针 fast = pHead; slow = pHead; int i = 0; for (i = 0; i < len; i++)//快指针先走环的长度 { fast = fast->Next; } while (fast != slow)//同时走，相遇即为入口 { fast = fast->Next; slow = slow->Next; } return fast; } int main() { /*构造一个带环的链表*/ ListNode* Node1 = CreateList(1); ListNode* Node2 = CreateList(2); ListNode* Node3 = CreateList(3); ListNode* Node4 = CreateList(4); ListNode* Node5 = CreateList(5); ListNode* Node6 = CreateList(6); connect(Node1, Node2); connect(Node2, Node3); connect(Node3, Node4); connect(Node4, Node5); connect(Node5, Node6); connect(Node6, Node3); ListNode* ret = EntranceNode(Node1); if (ret != nullptr) { cout << "链表的环入口节点为：" << ret->Data << endl; } else { cout << "传入指针为nullptr或者无环" << endl; } return 0; }
本章完！
文章知识点与官方知
