【链表系列 - 1】判断环形链表（快慢指针）_快慢指针判断链表是否有环

引言

给定一个链表，要求判断有没有环。

例题

【LEETCODE 141】

算法描述

一个显然的做法是从头开始往后扫，同时保存已经扫描到的节点，并且判断当前节点是否已经出现过，从而判断是否存在环。这种做法的空间复杂度$O(n)$，可以优化到$O(1)$。
用快慢指针法，两个指针一开始都从头节点开始，依次以步长为1和步长为2向后移动，由于快指针的移动速度更快，所以如果链表有环，快指针将再次追上慢指针，即可判断出有环。
也可以开始时慢指针在头节点，快指针在第二个节点，然后依次移动，追上时即可判断出有环。这两种做法前者可以用do-while语句，后者用while语句。
写法上注意一下判断空指针 nullptr 即可。

代码实现

//这里以第一种写法为例
class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto slow_ptr = head;
        auto quick_ptr = head;
        if (slow_ptr == nullptr) {
            return false;
        }
        do {
            if (quick_ptr->next == nullptr || quick_ptr->next->next == nullptr) {
                return false;
            }
            quick_ptr = quick_ptr->next->next;
            slow_ptr = slow_ptr->next;
        } while (slow_ptr != quick_ptr);
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

关键词

环形链表 快慢指针 双指针