958
[LeetCode]141.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?
【題意】
給定一個鏈表，確定它是否包含一個環。
【分析】
最容易想到的方法是，用一個哈希表 unordered_map<int, bool> visited，記錄每個元素是否被訪問過，一旦出現某個元素被重複訪問，說明存在環。
空間複雜度 O(n)，時間複雜度 O(N )。
最好的方法是時間複雜度 O(n)，空間複雜度 O(1) 的。設置兩個指針，一個快一個慢，快的指針每次走兩步，慢的指針每次走一步，如果快指針和慢指針相遇，則說明有環。
【代碼】
/*---------------------------------------------------------
* 日期：2015-04-23
* 作者：SJF0115
* 題目: 141.Linked List Cycle
* 網址：https://leetcode.com/problems/linked-list-cycle/
* 結果：AC
* 來源：LeetCode
* 博客：
------------------------------------------------------------*/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *slow = head,*fast = head;
while(fast != NULL && fast->next != NULL){
//慢指針走一步
slow = slow->next;
//快指針走兩步
fast = fast->next->next;
if(slow == fast){
return true;
}
}
return false;
}
};
最後更新：2017-04-03 12:54:51