剑指offer 链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

题目分析：

1）先判断是否有环。

快慢指针，同时从表头出发，一个每次走一步，另一个走两步。快慢指针能相遇，则说明有环，同时记录相遇的节点指针，否则直接返回null

2）我们知道快慢指针相遇的地方在环内，那么，我们以相遇的节点为起始，用另外一个指针遍历，当下一次再遇到这个相遇的节点，便知道环的节点数。因为是单链表，所以环的位置必然在最后，相当于我们要找的就是链表的倒数第k（环的节点个数）个节点。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6         val(x), next(NULL) {
 7     }
 8 };
 9 */
10 class Solution {
11 private:
12     ListNode* MeetingNode(ListNode* pHead) {
13         if (pHead == nullptr) {
14             return nullptr;
15         }
16         ListNode *slow = pHead;
17         bool flag = false;
18         if (slow->next == nullptr) {
19             return nullptr;
20         }
21         ListNode *fast = slow->next;
22         ListNode *meeting = nullptr;
23         while (fast != nullptr) {
24             if (fast == slow) {
25                 flag = true;
26                 meeting = fast;
27                 break;
28             }
29             slow = slow->next;
30             fast = fast->next;
31             if (fast != nullptr) {
32                 fast = fast->next;
33             } 
34         }
35         if (flag == true) {
36             return meeting;
37         } else {
38             return nullptr;
39         }
40     }
41 public:
42     ListNode* EntryNodeOfLoop(ListNode* pHead)
43     {
44         ListNode *meetingNode = MeetingNode(pHead);
45         if (meetingNode == nullptr) {
46             return nullptr;
47         }
48         //得到环中节点的数目
49         int nodesInLoop = 1;
50         ListNode *pNode1 = meetingNode;
51         while (pNode1->next != meetingNode) {
52             pNode1 = pNode1->next;
53             nodesInLoop++;
54         }
55         //先移动pNode1, 次数为环中节点的数目
56         pNode1 = pHead;
57         for (int i = 0; i < nodesInLoop; i++) {
58             pNode1 = pNode1->next;
59         }
60         //再同时移动pNode1和pNode2
61         ListNode *pNode2 = pHead;
62         while (pNode1 != pNode2) {
63             pNode1 = pNode1->next;
64             pNode2 = pNode2->next;
65         }
66         return pNode1;
67     }
68 };