/**

*

* @author gentleKay

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

* Follow up:

* Can you solve it without using extra space?

*

* 给定一个链表，确定它是否有一个循环。

* 跟进：

* 你能在不使用额外空间的情况下解决它吗？

*/

/** *  * @author gentleKay * Given a linked list, determine if it has a cycle in it. * Follow up: * Can you solve it without using extra space? *  * 给定一个链表，确定它是否有一个循环。 * 跟进： * 你能在不使用额外空间的情况下解决它吗？ */public class Main10 {	public static void main(String[] args) {		ListNode head = new ListNode(1);		head.next = new ListNode(2);		head.next.next = new ListNode(4);		head.next.next.next = new ListNode(6);		head.next.next.next.next = head;		System.out.println(Main10.hasCycle(head));	}		static class ListNode {		int val;		ListNode next;		ListNode(int x) {			val = x;			next = null;		}	}		public static boolean hasCycle(ListNode head) {		if (head == null) {			return false;		}		ListNode fast = head; // 两倍速度走		ListNode slow = head; // 一倍速度走   如果是一个循环的话，fast 肯定会与 slow 在相遇 ，并且相等。 如果不是循环的话，那 fast.next 就肯定会先 等于 null;        while (fast != null && fast.next != null) {  // 所以一定要判断两倍速度走的时候的下一个 fast.next 不为null        	fast = fast.next.next;        	slow = slow.next;        	if (fast == slow) {        		return true;        	}        }        return false;    }}