※剑指offer系列44：链表中环的入口结点

这个题要找到链表中的环的入口，很自然的可以分为两个问题。首先是判断链表中是否有环，其次寻找到环的入口。

1.判断是否有环，这里有两个指针。一个一次走一步，一个一次走两步。用这两个指针在链表上走，如果存在环两个指针一定会相遇，并且相遇的点是在环内。

这个很重要，判断链表是否存在环。

2.寻找环的入口。既然第一步已经找到了环的一个结点，从这个结点的位置开始走，一直到回到原点就是环的长度。有了环的长度，设置两个指针，第一个从链表头开始走，第二个从链表头先走环的长度开始走，两个指针相遇的结点就是环的入口。

 1 class Solution {
 2 public:
 3     ListNode* EntryNodeOfLoop(ListNode* pHead)
 4     {
 5         if (pHead == NULL)//链表结点不能为空
 6             return pHead;
 7         //找到在环中的结点
 8         ListNode *nodeinloop = findnodeinloop(pHead);
 9         if (nodeinloop == NULL)//如果没有环退出
10             return NULL;
11 
12         //从先在开始，一定有环
13         //计算环的长度
14         ListNode *tem = nodeinloop;
15         nodeinloop = nodeinloop->next;
16         int count = 1;//环的长度
17         while(nodeinloop != tem)
18         {
19             count++;
20             nodeinloop = nodeinloop->next;
21         }
22 
23         //设置两个指针开始找入口
24         ListNode *p1 = pHead;
25 
26         ListNode *p2 = pHead;//开始这里我写的是p2=pHead+count;结果牛客提示超时
27         for (int i = 0; i < count; i++)
28             p2 = p2->next;
29 
30         while (p1 != p2)
31         {
32             p1=p1->next; 
33             p2=p2->next;
34         }
35         return p1;
36     }
37     ListNode* findnodeinloop(ListNode* pHead)
38     {
39         if (pHead == NULL)
40             return NULL;
41         ListNode* pslow = pHead->next;
42         if (pslow == NULL)//说明只有一个结点，且没有环
43             return NULL;
44         ListNode* pfast = pslow->next;
45         while (pslow != NULL&&pfast != NULL)
46         {
47             if (pslow == pfast)
48                 return pslow;
49             pslow = pslow->next;//由于pfast不为空，所以它不用判断必定不是空
50             pfast = pfast->next;
51             if (pfast != NULL)//没到终点
52                 pfast = pfast->next;
53         
54 
55         }
56 
57         return NULL;
58     }
59 };

在26行我曾经写第二部的寻找环入口是直接用+count的方式想让链表的头结点走count步，结果我在我的编译器上没问题，但是牛客却显示超时了。可能是版本不支持吧。