剑指offer——面试题23：链表中环的入口节点

函数：

 1 ListNode* MeetingNode(ListNode* pHead)
 2 {
 3     if(pHead==nullptr)
 4         return nullptr;
 5     ListNode* quickNode=pHead;
 6     ListNode* slowNode=pHead;
 7 
 8     while(quickNode->m_pNext!=nullptr&&quickNode->m_pNext->m_pNext!=nullptr)
 9     {
10         quickNode=quickNode->m_pNext->m_pNext;
11         slowNode=slowNode->m_pNext;
12         if(quickNode==slowNode)
13             break;
14     }
15     if(quickNode!=slowNode)
16     {
17         return nullptr;
18     }
19     return slowNode;
20 }
21 
22 ListNode* EntryNodeOfLoop(ListNode* pHead)
23 {
24     ListNode* meetingNode=MeetingNode(pHead);
25     if(meetingNode==nullptr)
26         return nullptr;
27     int nodesInLoop=1;
28     ListNode* pTemp=meetingNode;
29     while(pTemp->m_pNext!=meetingNode)
30     {
31         pTemp=pTemp->m_pNext;
32         nodesInLoop++;
33     }
34     ListNode* quickNode=pHead;
35     ListNode* slowNode=pHead;
36     for(int i=0;i<nodesInLoop;i++)
37         quickNode=quickNode->m_pNext;
38     while(slowNode!=quickNode)
39     {
40         quickNode=quickNode->m_pNext;
41         slowNode=slowNode->m_pNext;
42     }
43     return slowNode;
44 }

View Code

测试代码：

 1 #include"List.h"
 2 
 3 void Test(char* testName,ListNode* pHead,ListNode* expect)
 4 {
 5     cout<<testName<<":";
 6     ListNode* result=EntryNodeOfLoop(pHead);
 7     if(result==nullptr)
 8     {
 9         cout<<"No loop in the link list."<<endl;
10     }
11     else if(result==expect)
12     {
13         cout<<"Passed."<<endl;
14     }
15     else
16         cout<<"Failed."<<endl;
17 }
18 
19 void Test1_7()
20 {
21     ListNode* pNode1=CreateListNode(1);
22     ConnectListNodes(pNode1,pNode1);
23     Test("test1",pNode1,pNode1);
24     ListNode* pNode2=CreateListNode(2);
25     ListNode* pNode3=CreateListNode(3);
26     ListNode* pNode4=CreateListNode(4);
27     ListNode* pNode5=CreateListNode(5);
28     ListNode* pNode6=CreateListNode(6);
29 
30     ConnectListNodes(pNode1,pNode2);
31     ConnectListNodes(pNode2,pNode3);
32     ConnectListNodes(pNode3,pNode4);
33     ConnectListNodes(pNode4,pNode5);
34     ConnectListNodes(pNode5,pNode6);
35     ConnectListNodes(pNode6,pNode3);
36     Test("test2",pNode1,pNode3);
37     ConnectListNodes(pNode6,pNode6);
38     Test("test3",pNode1,pNode6);
39     Test("test4",nullptr,nullptr);
40     ConnectListNodes(pNode6,nullptr);
41     Test("test5",pNode1,nullptr);
42     DestroyList(pNode1);//注意销毁所定义的指针和链表
43 }
44 
45 int main()
46 {
47     Test1_7();
48     return 0;
49 }

View Code

主要要销毁所定义的指针变量和链表。如果链表中存在环，则可以一个个节点去释放。