/**
 * 
 */
package com.fishercoder.solutions;

import com.fishercoder.common.classes.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 141. 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?
 *
 */
public class _141 {

	public boolean hasCycle(ListNode head) {
		ListNode slow = head, fast = head;
		while(fast != null && fast.next != null){
			fast = fast.next.next;
			slow = slow.next;
			if(fast == slow) return true;
		}
		return false;
	}

	public boolean hasCycle_using_hashtable(ListNode head) {
		Map<ListNode, Boolean> visited = new HashMap();
		ListNode temp = head;
		while(temp != null){
			if(visited.containsKey(temp)) return true;
			visited.put(temp, true);
			temp = temp.next;
		}
		return false;
	}

}

@@ -325,24 +325,59 @@
 s _141 %7B%0D%0A%0D%0A
+%09public static class Solution1 %7B%0D%0A%09
 %09public bool
@@ -405,24 +405,25 @@
  head) %7B%0D%0A%09%09
+%09
 ListNode slo
@@ -430,17 +430,30 @@
 w = head
-,
+;%0D%0A%09%09%09ListNode
  fast = 
@@ -461,21 +461,23 @@
 ead;%0D%0A%09%09
+%09
 while
+ 
 (fast !=
@@ -503,22 +503,24 @@
 != null)
+ 
 %7B%0D%0A%09%09%09
+%09
 fast = f
@@ -535,16 +535,17 @@
 .next;%0D%0A
+%09
 %09%09%09slow 
@@ -561,18 +561,20 @@
 xt;%0D%0A%09%09%09
+%09
 if
+ 
 (fast ==
@@ -592,27 +592,29 @@
 rn true;%0D%0A%09%09
+%09
 %7D%0D%0A
+%09
 %09%09return fal
@@ -614,24 +614,29 @@
 urn false;%0D%0A
+%09%09%7D%0D%0A
 %09%7D%0D%0A%0D%0A%09publi
@@ -641,38 +641,57 @@
 lic 
-boolean hasCycle_using_hashtab
+static class Solution2 %7B%0D%0A%09%09public boolean hasCyc
 le(L
@@ -709,16 +709,17 @@
 d) %7B%0D%0A%09%09
+%09
 Map%3CList
@@ -761,16 +761,17 @@
 p();%0D%0A%09%09
+%09
 ListNode
@@ -787,21 +787,23 @@
 ead;%0D%0A%09%09
+%09
 while
+ 
 (temp !=
@@ -812,16 +812,19 @@
 ull)
+ 
 %7B%0D%0A%09%09%09
+%09
 if
+ 
 (vis
@@ -861,16 +861,17 @@
  true;%0D%0A
+%09
 %09%09%09visit
@@ -894,16 +894,17 @@
 e);%0D%0A%09%09%09
+%09
 temp = t
@@ -914,23 +914,25 @@
 .next;%0D%0A
+%09
 %09%09%7D%0D%0A%09%09
+%09
 return f
@@ -938,16 +938,21 @@
 false;%0D%0A
+%09%09%7D%0D%0A
 %09%7D%0D%0A%0D%0A%7D%0D

edit 141