题目链接
题意
给一个链表, 若其中包含环, 请找出该链表的环的入口结点, 否则, 输出 null.
解题思路
入口节点即遍历过程第一个再次到达的节点.
第一步: 确定链表中包含环
方法: 两个指针同时从头节点出发, 一个每次一步, 一个每次两步. 如果走的快的指针追上了走的慢的, 说明有环. 如果走的快的指针走到了链表尾, 那么说明没环.
第二步: 找到环中的节点数
方法: 因为上述两个节点相遇的节点一定在环中, 所以从这个节点出发, 再次走到这个节点, 即可计算出环中的节点数.
第三步: 找到链表中环的入口节点
方法: 两个指针从链表头节点出发, 一个先走环的节点数步, 然后两个指针同时往前走, 两个指针相遇的节点即是环的入口节点.
总结:
三步的方法都很 666, 要多品读.
- class Solution {
- public:
- ListNode* EntryNodeOfLoop(ListNode* pHead)
- {
- if(!pHead){
- return nullptr;
- }
- // 找一个环中节点
- ListNode *pSlow=pHead->next;// 注意
- if(!pSlow){
- return nullptr;
- }
- ListNode *pFast=pSlow->next;
- while((pFast->next)->next&&pFast->next&&pFast!=pSlow ){// 注意
- pFast=(pFast->next)->next;
- pSlow=pSlow->next;
- }
- if(!(pFast->next)->next||!(pFast->next)){
- return nullptr;
- }
- // 计算环中节点数
- pFast=pFast->next;
- int cirCleNodeCnt=1;
- while(pFast!=pSlow){
- pFast=pFast->next;
- ++cirCleNodeCnt;
- }
- // 找环入口点
- pFast=pHead;
- pSlow=pHead;
- while(cirCleNodeCnt--){
- pFast=pFast->next;
- }
- while(pFast!=pSlow){
- pFast=pFast->next;
- pSlow=pSlow->next;
- }
- return pFast;
- }
- };
[剑指 Offer]23 - 链表中环的入口节点
来源: http://www.bubuko.com/infodetail-2978812.html