linkedListCycle

141. 环形链表

分析

初始化指针
- 如果链表为空或只有一个节点，则无法形成环，直接返回 false
- 设置两个指针 slow 和 fast，初始时都指向链表的头节点 head
移动指针
- 慢指针 slow 每次移动一步
- 快指针 fast 每次移动两步
- 每次移动后，检查 slow 和 fast 是否相等。如果相等，说明链表中存在环
终止条件
- 如果 fast 为 nullptr，说明链表没有环，直接返回 false

时间复杂度

慢指针最多遍历链表一次，快指针最多遍历链表两次，因此时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution
{
public:
    bool hasCycle(ListNode *head)
    {
        // 链表为空或只有一个节点，无法形成环
        if (!head || !head->next)
            return false;

        ListNode *slow = head, *fast = head;

        while (fast) // 快指针未到达链表末尾
        {
            slow = slow->next;           // 慢指针走一步
            fast = fast->next;           // 快指针走一步
            if (fast)
                fast = fast->next;       // 快指针再走一步

            if (slow == fast)            // 快慢指针相遇，存在环
                return true;
        }
        return false; // 快指针到达链表末尾，无环
    }
};