Linked List Cycle

循环链表

题目

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

解析重点

1.一开始只想到了hash table 的解决方案
2.后面参考官方，使用了双指针的方式，一个快指针，一个慢指针，如果是环形快指针一定可以追上慢指针

java代码

/**
  * 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;
    ListNode fast = head.next;
    while (slow != fast) {
      if (fast == null || fast.next == null) {
        return false;
      }
      slow = slow.next;
      fast = fast.next.next;
    }
    return true;
  }
}