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 static class Solution1 {
		public boolean hasCycle(ListNode head) {
			ListNode slow = head;
			ListNode fast = head;
			while (fast != null && fast.next != null) {
				fast = fast.next.next;
				slow = slow.next;
				if (fast == slow) {
					return true;
				}
			}
			return false;
		}
	}

	public static class Solution2 {
		public boolean hasCycle(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;
		}
	}

}

@@ -103,19 +103,19 @@
 til.Hash
-Map
+Set
 ;%0D%0Aimpor
@@ -126,19 +126,19 @@
 va.util.
-Map
+Set
 ;%0D%0A%0D%0A/**
@@ -166,16 +166,23 @@
  Cycle%0D%0A
+ *%0D%0A * 
 Given a 
@@ -402,24 +402,28 @@
 ) %7B%0D%0A%09%09%09
+Set%3C
 ListNode
  slow = 
@@ -418,168 +418,81 @@
 Node
+%3E
  s
-low = head;%0D%0A%09%09%09ListNode fast = head;%0D%0A%09%09%09while (fast != null && fast.next != null) %7B%0D%0A%09%09%09%09fast = fast.next.next;%0D%0A%09%09%09%09slow = slow.next;%0D%0A%09%09%09%09if (fast == slow
+et = new HashSet();%0D%0A%09%09%09while (head != null) %7B%0D%0A%09%09%09%09if (!set.add(head)
 ) %7B%0D
@@ -518,16 +518,39 @@
 %0A%09%09%09%09%7D%0D%0A
+%09%09%09%09head = head.next;%0D%0A
 %09%09%09%7D%0D%0A%09%09
@@ -661,20 +661,16 @@
 %0A%09%09%09
-Map%3C
 ListNode
 , Bo
@@ -669,42 +669,20 @@
 Node
-, Boolean%3E visited = new HashMap()
+ slow = head
 ;%0D%0A%09
@@ -692,20 +692,20 @@
 istNode 
-temp
+fast
  = head;
@@ -720,140 +720,146 @@
 le (
-temp != null) %7B%0D%0A%09%09%09%09if (visited.containsKey(temp)) %7B%0D%0A%09%09%09%09%09return true;%0D%0A%09%09%09%09%7D%0D%0A%09%09%09%09visited.put(temp,
+fast != null && fast.next != null) %7B%0D%0A%09%09%09%09fast = fast.next.next;%0D%0A%09%09%09%09slow = slow.next;%0D%0A%09%09%09%09if (fast == slow) %7B%0D%0A%09%09%09%09%09return
  true
-)
 ;%0D%0A%09%09%09%09
-temp = temp.next;
+%7D
 %0D%0A%09%09
@@ -889,13 +889,11 @@
 %09%7D%0D%0A%09%7D%0D%0A
-%0D%0A
 %7D%0D%0A

refactor 141