力扣刷题-热题100题-第25题（c++、python）

141. 环形链表 - 力扣（LeetCode）https://leetcode.cn/problems/linked-list-cycle/solutions/440042/huan-xing-lian-biao-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked

哈希法

c++中有unordered_set，python中有set，作为哈希的集合，遍历链表时，若当前指针在集合中就说明有环，返回true，否则将指针加入集合，最后若是正常退出循环表示没有环。

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

#python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        a=set()
        while head:
            if head in a:
                return True
            a.add(head)
            head=head.next
        return False

快慢指针

a走一步，b走两步，在存在环的情况下会有a能追上b，即a=b

所以循环的判断是a是否等于b，同时在循环里面有b不在末尾的空指针的判断（有空指针就代表肯定不是环形），退出循环就有a一定等于b，一定有环。

//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) {
        if(!head||!head->next)    return false;
        ListNode* s=head;
        ListNode* f=head->next;
        while(s!=f)
        {
            if(!f||!f->next)  return false;
            s=s->next;
            f=f->next->next;
        }
        return true;
    }
};

#python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        s=head
        f=head.next
        while s!=f:
            if not f.next or not f.next.next:
                return False
            s=s.next
            f=f.next.next
        return True