本文共 1087 字，大约阅读时间需要 3 分钟。

题目

题目描述判断给定的链表中是否有环。如果有环则返回true，否则返回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) {
           if(head==nullptr||head->next==nullptr)return false;        ListNode *slow=head,*fast=head->next;        //链表多长？        while(slow!=fast){
               if(fast==nullptr||slow==nullptr||fast->next==nullptr)return false;            slow=slow->next;            fast=fast->next->next;        }        return true;    }};

哈希表

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

转载地址：http://hzevi.baihongyu.com/