题目：环形链表

• 给定一个链表，判断链表中是否有环。
• 为了表示给定链表中的环，我们使用整数pos 来表示链表尾连接到链表中的位置（索引从0开始）。 如果pos是-1,则在该链表中没有环。

示例 1：

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

示例 2：

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

示例 3：

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

进阶：

• 你能用 O(1)（即，常量）内存解决此问题吗？

来源：力扣（LeetCode）第141题

链接：https://leetcode-cn.com/problems/linked-list-cycle

分析：

• 这道题可以使用哈希表来做，但这样的空间复杂度是O(n),另一种方法是快慢双指针。
• 使用两个指针，一个每次走一格，另一个每次走两格。
• 最后看快指针会不会走到头，或者这两个指针碰到了。

代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head, fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;fast = fast.next.next;
        }
        return true;
    }
}

• 使用set来做

  /**
  * Definition for singly-linked list.
  * class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int x) {
  *         val = x;
  *         next = null;
  *     }
  * }
  */
  public class Solution {
  public boolean hasCycle(ListNode head) {
      Set<ListNode> cycle = new HashSet();
      while (head != null) {
          if (cycle.contains(head)) return true;
          cycle.add(head);
          head = head.next;
      }
      return false;
  }
  }
  

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)