题目链接

题目描述

给定一个链表，判断链表中是否有环。

示例

示例1：

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

提示

  • 链表中节点的数目范围是 [0, 10]
  • -10 <= Node.val <= 10

  • pos 为 -1 或者链表中的一个 有效索引 。

    思路

    思路1：哈希表

    使用哈希表保存所有访问过的结点，每遍历一个结点，判断该结点是否在哈希表中，如果在表示有环。

    思路2：快慢指针

    设两个指针 slow 和 fast ，slow 每次移动一个结点，fast 每次移动两个结点，如果链表中有环，那么 fast 会提前进入换环中，等到 slow 进入环后，fast 总会追上 slow ，即俗说的套圈。

    题解

    思路2：快慢指针

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode(int x) : val(x), next(NULL) {}
    7. * };
    8. */
    9. class Solution {
    10.  public:
    11.   bool hasCycle(ListNode* head) {
    12.       ListNode* slow = head;
    13.       ListNode* fast = head;
    14.       while (fast != nullptr && fast->next != nullptr) {
    15.           slow = slow->next;
    16.           fast = fast->next->next;
    17.           if (slow == fast) {
    18.               return true;
    19.           }
    20.       }
    21.       return false;
    22.   }
    23. };

    复杂度分析

  • 时间复杂度：0141-环形链表 - 图1

  • 空间复杂度：0141-环形链表 - 图2