3.9面試?yán)}：空鏈表與循環(huán)鏈表
給定一個鏈表，它可能是以NULL結(jié)尾的非循環(huán)鏈表，如圖3-5所示；也可能是一個循環(huán)結(jié)構(gòu)結(jié)尾的循環(huán)鏈表。已知這個鏈表的頭指針，請編寫一個函數(shù)來判斷該鏈表是一個循環(huán)鏈表還是一個非循環(huán)鏈表，該函數(shù)不得對鏈表本身做任何修改。
算法：
讓快慢兩個指針從鏈表的頭元素出發(fā)開始遍歷
無限循環(huán)
如果快指針遇到了“NULL”指針
返回，該鏈表以“NULL”結(jié)束，是一個非循環(huán)鏈表
如果快指針追上或者超過了慢指針
返回，該鏈表是一個循環(huán)鏈表
讓慢指針前進(jìn)一個結(jié)點
讓快指針前進(jìn)兩個結(jié)點
int determineTermination(node *head) {
node *fast, *slow;
fast = slow = head;
for (;;) {
if (fast != null || fast->next != null)
return 0;
else if (fast == slow || fast->next == slow)
return 1;
else {
slow = slow->next;
fast = fast->next->next;
}
}
}
