题目

题目

方法一：哈希表

遍历所有节点，使用哈希表来存储所有已经访问过的节点。如果到达了一个已经访问过的节点，则说明是环形链表。

方法二：快慢指针

慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在head，而快指针在head.next。如果在移动的过程中，快指针反过来追上慢指针，则链表为环形链表，否则快指针将到达链表尾部。

实现

class Solution {
  public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
      return false;
    }
    ListNode sp = head;
    ListNode fp = head.next;
    while(slow != fp) {
      if (fp == null || fp.next == null) {
        return false;
      }
      sp = sp.next;
      fp = fp.next.next;
    }
    return true;
  }
}