package com.fishercoder.solutions;

import com.fishercoder.common.classes.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 141. Linked List Cycle

 Given a linked list, determine if it has a cycle in it.
 To represent a cycle in the given linked list, we use an integer
 pos which represents the position (0-indexed) in the linked list where tail connects to.
 If pos is -1, then there is no cycle in the linked list.

 Example 1:
 Input: head = [3,2,0,-4], pos = 1
 Output: true
 Explanation: There is a cycle in the linked list, where tail connects to the second node.

 Example 2:
 Input: head = [1,2], pos = 0
 Output: true
 Explanation: There is a cycle in the linked list, where tail connects to the first node.

 Example 3:
 Input: head = [1], pos = -1
 Output: false
 Explanation: There is no cycle in the linked list.

 Follow up:
 Can you solve it using O(1) (i.e. constant) memory?
 */
public class _141 {

	public static class Solution1 {
		public boolean hasCycle(ListNode head) {
			Set<ListNode> set = new HashSet();
			while (head != null) {
				if (!set.add(head)) {
					return true;
				}
				head = head.next;
			}
			return false;
		}
	}

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

@@ -138,874 +138,76 @@
 %0D%0A%0D%0A
-/**%0D%0A * 141. Linked List Cycle%0D%0A%0D%0A Given a linked list, determine if it has a cycle in it.%0D%0A To represent a cycle in the given linked list, we use an integer%0D%0A pos which represents the position (0-indexed) in the linked list where tail connects to.%0D%0A If pos is -1, then there is no cycle in the linked list.%0D%0A%0D%0A Example 1:%0D%0A Input: head = %5B3,2,0,-4%5D, pos = 1%0D%0A Output: true%0D%0A Explanation: There is a cycle in the linked list, where tail connects to the second node.%0D%0A%0D%0A Example 2:%0D%0A Input: head = %5B1,2%5D, pos = 0%0D%0A Output: true%0D%0A Explanation: There is a cycle in the linked list, where tail connects to the first node.%0D%0A%0D%0A Example 3:%0D%0A Input: head = %5B1%5D, pos = -1%0D%0A Output: false%0D%0A Explanation: There is no cycle in the linked list.%0D%0A%0D%0A Follow up:%0D%0A Can you solve it using O(1) (i.e. constant) memory?%0D%0A */%0D%0Apublic class _141 %7B%0D%0A%0D%0A%09public static class Solution1 %7B%0D%0A%09%09
+public class _141 %7B%0D%0A%0D%0A    public static class Solution1 %7B%0D%0A        
 publ
@@ -244,19 +244,28 @@
 ead) %7B%0D%0A
-%09%09%09
+            
 Set%3CList
@@ -292,19 +292,28 @@
 Set();%0D%0A
-%09%09%09
+            
 while (h
@@ -328,20 +328,32 @@
 ull) %7B%0D%0A
-%09%09%09%09
+                
 if (!set
@@ -371,93 +371,162 @@
  %7B%0D%0A
-%09%09%09%09%09return true;%0D%0A%09%09%09%09%7D%0D%0A%09%09%09%09head = head.next;%0D%0A%09%09%09%7D%0D%0A%09%09%09return false;%0D%0A%09%09%7D%0D%0A%09
+                    return true;%0D%0A                %7D%0D%0A                head = head.next;%0D%0A            %7D%0D%0A            return false;%0D%0A        %7D%0D%0A    
 %7D%0D%0A%0D%0A
-%09
+    
 publ
@@ -554,18 +554,24 @@
 ion2 %7B%0D%0A
-%09%09
+        
 public b
@@ -604,19 +604,28 @@
 ead) %7B%0D%0A
-%09%09%09
+            
 ListNode
@@ -639,19 +639,28 @@
  head;%0D%0A
-%09%09%09
+            
 ListNode
@@ -674,19 +674,28 @@
  head;%0D%0A
-%09%09%09
+            
 while (f
@@ -731,20 +731,32 @@
 ull) %7B%0D%0A
-%09%09%09%09
+                
 fast = f
@@ -771,20 +771,32 @@
 .next;%0D%0A
-%09%09%09%09
+                
 slow = s
@@ -806,20 +806,32 @@
 .next;%0D%0A
-%09%09%09%09
+                
 if (fast
@@ -847,64 +847,118 @@
  %7B%0D%0A
-%09%09%09%09%09return true;%0D%0A%09%09%09%09%7D%0D%0A%09%09%09%7D%0D%0A%09%09%09return false;%0D%0A%09%09%7D%0D%0A%09
+                    return true;%0D%0A                %7D%0D%0A            %7D%0D%0A            return false;%0D%0A        %7D%0D%0A    
 %7D%0D%0A%7D

refactor 141