讨论/算法和数据结构/如何判断链表中是否存在环?/
如何判断链表中是否存在环?
展开讨论
共 1 个讨论

image.png

解题思路:

方法一:穷举法
  • 一个检测指针 k,遍历指针 q,count 记录遍历指针q走的步数
  • 遍历指针每走一步,检测指针 k 就走遍历指针 q 之前走过的节点,若发现相同的节点便说明有环
  • 知道遍历节点 q 为 NULL 停止
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL)
            return false;
        ListNode *k=head;//检测节点
        ListNode *q=head->next;//遍历节点
        int count=0;//记录检测节点走了多少步
        while(q)
        {
            for(int i=count;i>0;i--)
            {
                k=k->next;
                if(k==q)
                    return true;
            }
            k=head;//还原
            q=q->next;
            count++;
        }
        return false;
    }
};

复杂度分析:
检测节点 k 移动的次数远远大于遍历节点,当链表不存在环时,检测节点的移动次数为 1+2+3+...+n1+2+3+...+n,计算可以直到时间复杂度为 O(n2)O(n^2),空间复杂度为 O(1)O(1)

方法二:标记
  • 在链表中增加一个数据域 visit 标记节点是否被遍历过,LinkList.visit = true 时说明该节点被遍历过,若遇到了遍历过的节点说明链表有环。
  • visit 初始化为 false
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     bool visit;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *q=head;
        while(q)
        {
            if(q->visit==true)
                return true;
            else
                q->visit=true;
        }
        return false;
    }
};

注:这方法在力扣上不能编译,因为默认的链表数据域是没有 visit 的

复杂度分析:
若存在环,只需要遍历到第 n+1 次,故时间复杂度为 O(n)O(n),空间复杂度是 O(n)O(n)

方法三:快慢指针
  • 初始化 slow = head->next,每次走一步
  • 初始化 fast =head->next->next,每次走两步,每走一步判断一次
  • 存在环 fast 和 slow 会相遇
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL)
            return false;
        ListNode *fast=head->next->next;
        ListNode *slow=head->next;
        while(fast)
        {
            slow=slow->next;
            for(int i=0;i<2;i++)
            {
                if(fast->next==NULL)
                    return false;
                fast=fast->next;
                if(fast==slow)
                    return true;
            }
        }
        return false;
    }
};

复杂度分析:
时间复杂度:O(n)O(n)。除了两个指针以外,没有使用任何额外存储空间,所以空间复杂度是 O(1)O(1)

方法四:set 集合大小变化
  • 利用集合的性质,去重
  • 若有环,就会重复插入相同的节点,那么 set 大小不会发生变化
  • 若 set 大小没有发生变化,那么说明存在环
class Solution {
public:
    bool hasCycle(ListNode *head) {
        set<ListNode*> a;
        ListNode *q=head;
        int count=0;//记录set的大小
        while(q)
        {
            a.insert(q);
            if(count==a.size())
                return true;
            q=q->next;
            count=a.size();
        }
        return false;
    }
};

复杂度分析:
时间复杂度:O(n)O(n)
空间复杂度:O(n)O(n)

16