Algorithm One Day One -- 判断链表是否有环(下)

/******************************************************************** created:2015年1月23日 00:34:45 author: Jackery purpose: Is there a loop ? 《Continue》 *********************************************************************/ //计算环的长度 /*对其中的stepfast与stepslow能与能相遇这个问题，不太好理解，触及到 类似欧拉回路的问题，胡运权的运筹学上面有相干类似讲授，不过 你完全可以写个小demo去验证，对这个换是奇数、偶数我都验证了 ，都是可行的*/ int LoopLength(pNode pHead) { if(isLoop(pHead) == false) return 0; pNode stepfast = pHead; pNode stepslow = pHead; int length = 0; bool begin = false; bool agian = false; while( stepfast != NULL && stepfast->next != NULL) { stepfast = stepfast->next->next; stepslow = stepslow->next; //超两圈后停止计数，跳出循环 if(stepfast == stepslow && agian == true) break; //超1圈后开始计数 if(stepfast == stepslow && agian == false) { begin = true; agian = true; } //计数 if(begin == true) ++length; } return length; } //求出环的入口点 Node* FindLoopEntrance(pNode pHead) { pNode stepfast = pHead; pNode stepslow = pHead; while( stepfast != NULL && stepfast->next != NULL) { stepfast = stepfast->next->next; stepslow = stepslow->next; //如果有环，则stepfast会超过stepslow1圈 if(stepfast == stepslow) { break; } } if(stepfast == NULL || stepfast->next == NULL) return NULL; stepslow = pHead; while(stepslow != stepfast) { stepslow = stepslow->next; stepfast = stepfast->next; } return stepslow; }