leetcode題解——環(huán)形鏈表

題目如下

給定一個鏈表，判斷鏈表中是否有環(huán)。

如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進行傳遞，僅僅是為了標(biāo)識鏈表的實際情況。

如果鏈表中存在環(huán)，則返回 true 。 否則，返回 false 。

進階：你能用 O(1)（即，常量）內(nèi)存解決此問題嗎？

解題思路

• 有兩種解題思路：1. 雙指針法；2. 哈希表法

1. 雙指針法：設(shè)置快慢兩個指針，快指針每次走兩步，慢指針每次走一步，若有環(huán)，則一定會在某個時刻，快慢指針在環(huán)內(nèi)相遇。
2. 哈希表法：設(shè)置哈希表來記錄所有遍歷過的結(jié)點，若有環(huán)，一定會遍歷到重復(fù)的結(jié)點。

有點意思

我原本以為哈希表法的速度會比雙指針法快，結(jié)果是我錯付了。仔細一想應(yīng)該是存表的時間消耗太多了

//c語言，雙指針法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast!=NULL && fast->next!=NULL){
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast){
            return true;
        }
    }
    return false;
}

//c++,哈希表法
/**
 * 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) {
        unordered_set<ListNode*> seen;
        while (head != nullptr) {
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
        return false;

    }
};