[LeetCode]Linked List Cycle
原题链接：http://oj.leetcode.com/problems/linked-list-cycle/
题意描述：
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
题解：
判断一个单链表中是否有环，这是一道典型的快慢指针的题，具体概念参见百度：http://baike.baidu.com/link?url=6vrn7yMJjWonSHrzGNLZA16JoJZxrLkFuRtJH3oP3PHCBakSKKM2UQH-5xtM9evvEGE385f7Ry9lqsn_Q0AKua
其实理解起来很简单，就是设置两个指针，步长不同，形成一个“追赶”另一个的情形，如果两个相遇了，那么肯定有环，如果有一个变成了NULL(肯定是快的那个)，那么就不存在环。
当然也有其他解法，比如比较到达某一顶点的步数，步数多的，肯定是绕了环，其实本质都差不多。
这道题还有一个加强版，假如存在环，找到环的起点。http://www.cnblogs.com/codershell/p/3600958.html
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 bool hasCycle(ListNode *head) { 12 if(head==NULL)return false; 13 ListNode*p = head,*q = head; 14 while(p!=NULL && q!=NULL){ 15 p = p->next; 16 q = q->next; 17 if(q!=NULL) 18 q = q->next; 19 else 20 return false; 21 22 if(p==q) 23 return true; 24 25 } 26 return false; 27 } 28 };