Given a linked list, determine if it has a cycle in it.
Can you solve it without using extra space?
每个节点再开辟一个属性存放是否访问过，这样遍历一遍即可知道是否有环。
但为了不增加额外的空间，
可以设置两个指针，一个一次走一步，另一个一次走两步，如果有环则两个指针一定会再次相遇，反之则不会。
C++:
1 class Solution { 2 public: 3 bool hasCycle(ListNode *head) { 4 if(head==NULL||head->next==NULL) return 0; 5 6 ListNode *p=head; 7 ListNode *q=head; 8 int flag=0; 9 while(p->next) 10 { 11 if(p->next==q) 12 { 13 flag=1; 14 break; 15 } 16 p=p->next; 17 if(p->next==NULL) 18 break; 19 p=p->next; 20 q=q->next; 21 } 22 if(flag==1) 23 return 1; 24 else 25 return 0; 26 } 27 };
Python：
1 # Definition for singly-linked list. 2 # class ListNode: 3 # def __init__(self, x): 4 # self.val = x 5 # self.next = None 6 7 class Solution: 8 # @param head, a ListNode 9 # @return a boolean 10 def hasCycle(self, head): 11 if head is None: 12 return False 13 p1=head 14 p2=head 15 while True: 16 if p1.next is not None: 17 p1=p1.next.next 18 p2=p2.next 19 if p1 is None or p2 is None: 20 return False 21 elif p1==p2: 22 return True 23 else: 24 return False 25 return False
原文：http://www.cnblogs.com/jawiezhu/p/4401072.html