add a solution for 142

fishercoder1534 · fishercoder1534 · commit d772b0e6c238 · 2021-10-24T10:00:18.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_142.java b/src/main/java/com/fishercoder/solutions/_142.java
@@ -2,9 +2,35 @@
 
 import com.fishercoder.common.classes.ListNode;
 
+import java.util.HashSet;
+import java.util.Set;
+
 public class _142 {
 
     public static class Solution1 {
+        public ListNode detectCycle(ListNode head) {
+            Set<ListNode> seen = new HashSet<>();
+            while (head != null) {
+                if (!seen.add(head)) {
+                    return head;
+                }
+                head = head.next;
+            }
+            return null;
+        }
+    }
+
+    public static class Solution2 {
+        /**
+         * This comment explains it really well for this solution:
+         * https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O(1)-space-solution-with-detailed-explanation./44281
+         *
+         * When fast and slow meet for the first time at point P, fast travelled (a + b + c + b)
+         * and slow travelled (a + b), and we know fast travels twice fast as slow, so we have:
+         * a + b + c + b = 2*(a + b), this gives us a == c;
+         * so at point P, we start a new slow2 pointer from the head, when both slow and slow2 travelled distance a, they must meet
+         * at cycle entrance point Q.
+         */
         public ListNode detectCycle(ListNode head) {
             ListNode slow = head;
             ListNode fast = head;
