141. 环形链表 – Blog of Aspirer

题目链接：https://leetcode.cn/problems/linked-list-cycle/

一开始被题目里的pos误导了，后面直接看了官方题解，让我做感觉不一定做得出来，第一种方法估计会想不到增加一个set或者map或者vector保存链表节点的地址，第二种方法更想不到。

/**
 * 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*> set;
        while (head) {
            if (set.count(head)) {
                return true;
            }
            set.insert(head);
            head = head->next;
        }
        return false;
    }
*/

    bool hasCycle(ListNode *head) {
        if (!head || !head->next) {
            return false;
        }
        
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            if (slow == fast) {
                return true;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return false;
    }

};

/**

* 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*> set;

while (head) {

if (set.count(head)) {

return true;

}

set.insert(head);

head = head->next;

}

return false;

}

bool hasCycle(ListNode *head) {

if (!head || !head->next) {

return false;

}

ListNode* slow = head;

ListNode* fast = head->next;

while (fast && fast->next) {

if (slow == fast) {

return true;

}

slow = slow->next;

fast = fast->next->next;

}

return false;

}

};