题目：

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

分析：

检查链表是否有圈。

题目要求不能使用多余的空间。于是这里使用Floyd判圈算法，又称龟兔赛跑算法。算法逻辑如下：

指针hare初始化指向链表头结点，每次向后移动2个节点。
指针tortoise初始化指向链表头结点，每次向后移动1个节点。
如果hare最终指向尾节点或尾节点前一个节点（总结点数可能是奇数也可能是偶数），则该链表无圈。
如果hare和tortoise又指向了同一个节点，则该链表有圈。

通俗点的解释就是：龟兔赛跑，如果是一条直线，兔子永远会跑在前面；如果兔子发现又追上乌龟了，那么只能是兔子套了乌龟一圈。

代码：

bool hasCycle(struct ListNode *head) {
	if (head == NULL) return 0;
	struct ListNode *hare = head;
	struct ListNode *tortoise = head;
	while (hare->next != NULL && hare->next->next != NULL){
		hare = hare->next->next;
		tortoise = tortoise->next;
		if (hare == tortoise) return 1;
	}
	return 0;
}