這道題不能用go寫峰髓，所以用C語(yǔ)言寫的
題目
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
解題思路
判斷鏈表有沒(méi)有環(huán)，用快慢指針?lè)?br> 一個(gè)慢指針，每次向下走一步牡肉，一個(gè)快指針，每次向后走兩步，如果鏈表有環(huán)，兩個(gè)指針就會(huì)相遇潜支，如果沒(méi)環(huán)，最終會(huì)走到鏈表末尾
證明
如果鏈表有環(huán)柿汛，設(shè)鏈表長(zhǎng)度為N冗酿，其中一段在環(huán)外，長(zhǎng)度為l，一段在環(huán)內(nèi)裁替，長(zhǎng)度為o,有
N = l + o
快慢指針走了i次之后项玛，如果相遇，則有
il + jo = 2i(l+o)
jo = il + 2io
j = i(l+2o)/o
所以i為o時(shí)弱判，兩個(gè)鏈表肯定相遇
代碼
/**
* 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;
}
}
