/******************************************************************** 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; }