生活随笔
收集整理的這篇文章主要介紹了
剑指offer（C++）——链表中环的入口结点
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
代碼如下：
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};/*思路：設置兩個指針p1和p2，如果鏈表中有n個結點，指針p1先向前移動n個結點，然后兩個指針以相同速度向前移動，當兩個指針相遇的結點就是環(huán)的入口結點。
如何統(tǒng)計環(huán)中結點個數n：設置一快一慢兩個指針pSlow和pFast，如果鏈表中有環(huán)，兩指針必定在環(huán)中某個結點出相遇。從此結點開始計數，當再次到達此結點時，就可以得到環(huán)中結點數*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead){if (pHead == NULL)return NULL;ListNode* meetingNode = MeetingNode(pHead); //找到環(huán)中的一個結點if (meetingNode == NULL)return NULL;int countNode = 1;ListNode* pNode1 = meetingNode;while (pNode1->next != meetingNode) //統(tǒng)計環(huán)中結點個數{pNode1 = pNode1->next;++countNode;}pNode1 = pHead;for (int i = 0; i < countNode;i++)//快慢指針，速度一致，但是起始不同，快指針先走countNode個節(jié)點pNode1 = pNode1->next;ListNode* pNode2 = pHead;while (pNode1 != pNode2){pNode1 = pNode1->next;pNode2 = pNode2->next;}return pNode1;}/*此函數用來找到環(huán)中的一個結點*/ListNode* MeetingNode(ListNode* pHead){if (pHead == NULL)return NULL;ListNode* pSlow = pHead;ListNode* pFast = pSlow->next;if (pFast == NULL)return NULL;while (pSlow != NULL&&pFast != NULL){if (pFast == pSlow)return pFast;pSlow = pSlow->next;pFast = pFast->next;if (pFast != NULL)pFast = pFast->next;}return NULL;}
};
總結
以上是生活随笔為你收集整理的剑指offer（C++）——链表中环的入口结点的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
