题目：
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
代码：
用hashmap版
/**
* 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) {
std::map<ListNode *, bool> ifNodeOccured;
ListNode *p = head;
while ( p )
{
if ( ifNodeOccured.find(p) != ifNodeOccured.end() ) return true;
ifNodeOccured.insert(std::pair<ListNode *, bool>(p,true));
p = p->next;
}
return false;
}
};
不用hashmap，改用双指针技巧版
/**
* 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) return false;
ListNode *p1 = head;
ListNode *p2 = head;
while ( p2->next && p2->next->next )
{
p2 = p2->next->next;
p1 = p1->next;
if (p2==p1) return true;
}
return false;
}
};
Tips：
这两种解法都是基本的技巧。第二种双指针的技巧效率更高，且空间复杂度更低，似乎得到了更多的推崇；但个人总觉得hashmap的方法不错，而且不强依赖于技巧。
==============================================
第二次过，用双指针技巧过的。第一次没有AC，因为忘记了dummpy.next = head这句；第二次AC了。
/**
* 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) {
ListNode dummpy(-);
dummpy.next = head;
ListNode* p1 = &dummpy;
ListNode* p2 = &dummpy;
while ( p2 )
{
p1 = p1->next;
p2 = p2->next;
if ( !p2 ) return false;
p2 = p2->next;
if ( p1==p2 ) return true;
}
return false;
}
};