Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
分析：这道题限制条件是不可以用额外空间，然而我们就不能需求用栈或队列来求解了。我们换一种思路，使用两个指针，一个是走的比较快一次走两步，另一个是走的比较慢一次走一步，如果快的指针追上慢指针说明有环，否则没有。
C++代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { if(head==NULL||head->next==NULL) return false; ListNode* behind=head; ListNode* ahead=head->next; while(ahead->next!=NULL) { ahead=ahead->next; if(ahead==NULL) return false; if(behind==ahead) return true; ahead=ahead->next; if(ahead==NULL) return false; if(ahead==behind) return true; behind=behind->next; if(behind==ahead) return true; } } };
Linked List Cycle,布布扣,bubuko.com
原文：http://www.cnblogs.com/awy-blog/p/3577255.html