原题地址（简单）

方法1—双指针

思路

此题是Floyd龟兔赛跑算法的典型应用，使用龟兔赛跑算法的第一阶段即可解决。
强烈建议您看一下本文，看完后不仅能拿下本题，还可以进一步拿下环形链表II。

Floyd龟兔赛跑算法

也就是快慢指针，慢指针一次一步，快指针一次两步，如果有环，则一定相遇

python代码

  1. def hasCycle(self, head: ListNode) -> bool:
  2.     fast = slow = head
  3.     while fast and slow:
  4.         if fast.next:
  5.             fast = fast.next.next
  6.         else:
  7.             return False
  8.         slow = slow.next
  9.         if fast == slow:
  10.             return True
  11.     return False

时间复杂度O(n)

  1. 如果无环，快指针走到头，就是O(n)
  2. 如果有环
    • 假设环前有n个元素，环中有m个元素，当慢指针走到环的起点时(走了n步)，这时快指针除了在环前走的n步，还在环内走了n步。
    • 如果给环中元素按起点顺时针顺序标号(起点为0号，依次为1,2,3,….,m-1号)，则此时快指针在环内的n mod m号元素上，我们记为第k号元素，而慢指针在第0号元素上。
    • 慢指针在第0号元素，快指针在第k号元素，快指针比慢指针走的快，由于是个环，所以可以看成慢指针在快指针前面，并且领先m-k步。
    • 慢指针领先快指针m-k步，由于快指针速度是慢指针两倍，所以轻易得知，经过m-k次迭代，也就是说慢指针走了m-k步，快指针走了2(m-k)步，两者相遇。
    • 而这个m-k，由于是环中的部分长度，所以一定小于n，所以时间为O(n+(m-k))，也就是O(n)

空间复杂度O(1)

方法2—哈希表

思路

遍历这个链表，将遍历到的元素依次扔到哈希表里，每次先判断哈希表有无该元素。

如果存在循环，一定能找到一个元素，哈希表中已经存在，直接break，结束；
如果不存在循环，遍历完毕，直接返回False

注意：哈希表中存的是节点，而不是节点值。如果存节点值，无法解决[1,2,2,3]这样的情况

cpp代码

  1. bool hasCycle(ListNode *head) {
  2.     set<ListNode*> s;
  3.     ListNode *p=head;
  4.     while(p)
  5.     {
  6.         if(s.find(p)!=s.end())  return true;
  7.         else    s.insert(p);
  8.         p = p->next;
  9.     }
  10.     return false;
  11. }

python代码

  1. def hasCycle(self, head: ListNode) -> bool:
  2.     p = head
  3.     shash = set([])
  4.     while p:
  5.         if p in shash:
  6.             return True
  7.         shash.add(p)
  8.         p = p.next
  9.     return False

时间复杂度O(n)

空间复杂度O(n)