程序员面试攻略　3.9 面试例题：空链表与循环链表

3.9面试例题：空链表与循环链表
给定一个链表，它可能是以NULL结尾的非循环链表，如图3-5所示；也可能是一个循环结构结尾的循环链表。已知这个链表的头指针，请编写一个函数来判断该链表是一个循环链表还是一个非循环链表，该函数不得对链表本身做任何修改。
算法：

让快慢两个指针从链表的头元素出发开始遍历
无限循环
 如果快指针遇到了“NULL”指针
  返回，该链表以“NULL”结束，是一个非循环链表
 如果快指针追上或者超过了慢指针
  返回，该链表是一个循环链表
 让慢指针前进一个结点
 让快指针前进两个结点

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