题目：一个链表中包含环，如何找出环的入口结点？例如，在图8.3的链表中，环的入口结点是结点3。
思路：定义两个指针p1,p2都指向头结点，假设链表中有n个结点，先让p1先走n个结点，然后让p1,p2同时走，当两个指针相遇时，相遇的结点就是环的入口结点。
解题步骤：(1)：先判断链表中是否包含环。定义两个指针，一个慢指针每次走1步，一个快指针每次走2步，当两个指针能相等时，也就是相遇，链表中就含有环。(2)：计算出环的结点数。用(1)中相遇的结点再继续走，定义一个变量n每次进行自增，当能碰到它自己的话，n就是环的结点数。(3)：用思路进行计算即可。
#include#include #include using namespace std;struct ListNode{ int m_nValue; ListNode* m_pNext;};ListNode* CreateListNode(int value){ ListNode* node = new ListNode(); node->m_nValue = value; node->m_pNext = NULL; return node;}void ConnectListNodes(ListNode* node1, ListNode* node2){ if (node1 != NULL && node2 != NULL) { node1->m_pNext = node2; }}void PrintListNode(ListNode* pHead){ if (pHead == NULL) { return; } if (pHead != NULL) { cout << pHead->m_nValue << " "; pHead = pHead->m_pNext; } cout << endl;}void DestroyList(ListNode* pHead){ ListNode* node = pHead; while (node != NULL) { pHead = pHead->m_pNext; delete node; node = pHead; }}ListNode* MeetingNode(ListNode* pHead){ if (pHead == NULL) { return NULL; } ListNode* pSlow = pHead->m_pNext; if (pSlow == NULL) { return NULL; } ListNode* pFast = pSlow->m_pNext; while (pFast != NULL && pSlow != NULL) { if (pFast == pSlow) { return pFast; } pSlow = pSlow->m_pNext; pFast = pFast->m_pNext; if (pFast != NULL) { pFast = pFast->m_pNext; } } return NULL;}ListNode* EntryNodeOfLoop(ListNode* pHead){ ListNode* meetingNode = MeetingNode(pHead); if (meetingNode == NULL) { return NULL; } int nodesInLoop = 1; ListNode* pNode1 = meetingNode; while (pNode1->m_pNext != meetingNode) { pNode1 = pNode1->m_pNext; ++nodesInLoop; } pNode1 = pHead; for (int i = 0; i < nodesInLoop; i++) { pNode1 = pNode1->m_pNext; } ListNode* pNode2 = pHead; while (pNode1 != pNode2) { pNode1 = pNode1->m_pNext; pNode2 = pNode2->m_pNext; } return pNode1;}void test1(){ ListNode* node1 = CreateListNode(1); ListNode* node2 = CreateListNode(2); ListNode* node3 = CreateListNode(3); ListNode* node4 = CreateListNode(4); ListNode* node5 = CreateListNode(5); ListNode* node6 = CreateListNode(6); ListNode* node7 = CreateListNode(7); ConnectListNodes(node1, node2); ConnectListNodes(node2, node3); ConnectListNodes(node3, node4); ConnectListNodes(node4, node3); ListNode* node = EntryNodeOfLoop(node1); PrintListNode(node);}int main(){ test1(); return 0;}