这道题不能用go写，所以用C语言写的
题目
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
解题思路
判断链表有没有环，用快慢指针法
一个慢指针，每次向下走一步，一个快指针，每次向后走两步，如果链表有环，两个指针就会相遇，如果没环，最终会走到链表末尾
证明
如果链表有环，设链表长度为N，其中一段在环外，长度为l，一段在环内，长度为o,有
N = l + o
快慢指针走了i次之后，如果相遇，则有
il + jo = 2i(l+o)
jo = il + 2io
j = i(l+2o)/o
所以i为o时，两个链表肯定相遇
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
if (NULL == head)
return false;
struct ListNode *l1, *l2;
l1 = l2 = head;
while (1) {
if (NULL == l1->next) {
return false;
} else
l1 = l1->next;
if (NULL == l2->next || NULL == l2->next->next) {
return false;
} else
l2 = l2->next->next;
if (l1 == l2)
return true;
}
}
