题目

链表定义：

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

题解

142的简化版，202的方法来源

1. 快慢指针法

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$
class Solution {//两种方法，这题关键在于判断什么时候返回true。1、快慢指针法
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;//设置快慢指针，都指向链表头
        while(fast && fast->next){
        //若快指针不为空，则继续迭代，同时要判断fast->next不为空，否则不能fast->next->next
            slow = slow->next;//慢指针一次从一位
            fast = fast->next->next;//快指针一次动两位
            if(slow == fast) return true;//若快指针追上慢指针，说明有环，注意要先移动再判断
        }
        return false;//若跳出循环，返回false
    }
};

2. 无序链表法

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$
class Solution {//两种方法。2、无序列表法，即将遍历的每个值存入set，若遇到重复则返回true
                //需要额外空间
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> m;//创建无续set存遍历过的值
        ListNode *cur = head;//cur指针指向链表头
        while(cur){//当cur存在，继续遍历
            if(m.count(cur)) return true;//如果存在遍历过的值，则返回true
            m.insert(cur);//set种处插入当前值
            cur = cur->next;//指针后移
        }
        return false;
    }
};