leetcode：141. 环形链表

题目

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：
[简单] 141. 环形链表 - 图1

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

示例 2：
[简单] 141. 环形链表 - 图2

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

示例 3：
[简单] 141. 环形链表 - 图3

  1. 输入：head = [1], pos = -1
  2. 输出：false
  3. 解释：链表中没有环。

解答 & 代码

快慢指针：

  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* fast = head;    // 快指针
  13.         ListNode* slow = head;    // 慢指针
  14.         while(fast != NULL && fast->next != NULL)
  15.         {
  16.             fast = fast->next->next;    // 快指针走两步
  17.             slow = slow->next;            // 慢指针走一步
  18.               // 如果两个指针相遇，说明链表中有环
  19.             if(fast == slow)
  20.                 return true;
  21.         }
  22.           // fast 走到了链表尾部，说明链表没有环
  23.         return false;
  24.     }
  25. };

复杂度分析：

  • 时间复杂度 O(N)
  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 99.75% 的用户
  4. 内存消耗：7.9 MB, 在所有 C++ 提交中击败了 65.34% 的用户