这道题是纪念版里的题目，之前没有见过，非常惭愧，经室友指点才做出来。
思路是这样的:首先要求它们相遇的节点，然后根据相遇的节点推算出环的长度 l（让一个新的指针在转一圈），最后定义一前一后两个指针，前面的指针先走 l 步，然后前后一起走，直到相遇。
所以这道题其实是将两个题目的思路给融合到了一起，一个是寻找链表中倒数第 n 个节点（第 15 题），一个是判断一个链表是否有环（15 题后面的参考题目）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode* meetNode=this->GetMeetNode(pHead);
if(meetNode==NULL){
return NULL;
}
int loopNumber=this->GetLoopNumber(meetNode);
return this->GetEntryNode(pHead,loopNumber);
}
ListNode* GetMeetNode(ListNode* pHead){
if(pHead==NULL || pHead->next==NULL ){
return NULL;
}
ListNode* pSlow=pHead;
ListNode* pFast=pHead->next->next;
while(pSlow!=NULL && pFast!=NULL){
if(pFast==pSlow){
return pSlow;
}
pSlow=pSlow->next;
if(pFast->next!=NULL){
pFast=pFast->next->next;
}
}
return NULL;
}
int GetLoopNumber(ListNode* meetNode){
int loopNumber=1;
ListNode* testNode=meetNode->next;
while(testNode!=meetNode){
testNode=testNode->next;
loopNumber++;
}
return loopNumber;
}
ListNode* GetEntryNode(ListNode* pHead,int loopNumber){
ListNode* pSlow=pHead;
ListNode* pFast=pHead;
for(int i=0;i<loopNumber;i++){
pFast=pFast->next;
}
while(pSlow!=pFast){
pSlow=pSlow->next;
pFast=pFast->next;
}
return pSlow;
}
};
|
代码除了一个编译错误以外，一遍通过，还是很开心的。