01
06/2015
[LeetCode] Linked List Cycle
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?
解题思路：
1、最基本的办法是用一个set来存储所有已经出现过的指针。若出现重复，则表示有环，若没有重复，则没有环。
/**
* 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* p = head;
set<ListNode*> s;
while(p!=NULL){
if(s.find(p)!=s.end()){
return true;
}
s.insert(p);
p=p->next;
}
return false;
}
};2、双指针方法。设立两个指针，一个指针每次走一步，另外一个指针每次走两步。若两个指针相遇，表示有环。不相遇，则表示无环。具体见：http://blog.csdn.net/kangrydotnet/article/details/45154927
/**
* 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* one = head;
ListNode* two = head;
while(two!=NULL && two->next!=NULL){
one=one->next;
two=two->next->next;
if(one==two){
return true;
}
}
return false;
}
};转载请注明：康瑞部落 » [LeetCode] Linked List Cycle
0 条评论