Linked list cycle (examplehub#93)

realDuYuanChao · github-actions · web-flow · commit 3f185cd27286 · 2021-04-06T09:07:32.000+08:00
* linked-list-cycle

* Formatted with Google Java Formatter

Co-authored-by: github-actions &lt;${GITHUB_ACTOR}@users.noreply.github.com&gt;
diff --git a/src/main/java/com/examplehub/leetcode/easy/LinkedListCycle.java b/src/main/java/com/examplehub/leetcode/easy/LinkedListCycle.java
@@ -0,0 +1,35 @@
+package com.examplehub.leetcode.easy;
+
+import com.examplehub.leetcode.ListNode;
+import java.util.HashSet;
+import java.util.Set;
+
+/** https://leetcode.com/problems/linked-list-cycle/ */
+public class LinkedListCycle {
+  public static boolean solution1(ListNode head) {
+    Set<ListNode> sets = new HashSet<>();
+    while (head != null) {
+      if (!sets.add(head)) {
+        return true;
+      }
+      head = head.next;
+    }
+    return false;
+  }
+
+  public static boolean solution2(ListNode head) {
+    if (head == null || head.next == null) {
+      return false;
+    }
+    ListNode slow = head;
+    ListNode fast = head.next;
+    while (slow != fast) {
+      if (fast == null || fast.next == null) {
+        return false;
+      }
+      slow = slow.next;
+      fast = fast.next.next;
+    }
+    return true;
+  }
+}
diff --git a/src/test/java/com/examplehub/leetcode/easy/LinkedListCycleTest.java b/src/test/java/com/examplehub/leetcode/easy/LinkedListCycleTest.java
@@ -0,0 +1,52 @@
+package com.examplehub.leetcode.easy;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.examplehub.leetcode.ListNode;
+import org.junit.jupiter.api.Test;
+
+class LinkedListCycleTest {
+  @Test
+  void testSolution1() {
+    ListNode head = new ListNode(3);
+    ListNode node2 = new ListNode(2);
+    ListNode node3 = new ListNode(0);
+    ListNode node4 = new ListNode(4);
+    head.next = node2;
+    node2.next = node3;
+    node3.next = node4;
+    node4.next = node2;
+    assertTrue(LinkedListCycle.solution1(head));
+
+    head = new ListNode(1);
+    node2 = new ListNode(2);
+    head.next = node2;
+    node2.next = head;
+    assertTrue(LinkedListCycle.solution1(head));
+
+    head = new ListNode(1);
+    assertFalse(LinkedListCycle.solution1(head));
+  }
+
+  @Test
+  void testSolution2() {
+    ListNode head = new ListNode(3);
+    ListNode node2 = new ListNode(2);
+    ListNode node3 = new ListNode(0);
+    ListNode node4 = new ListNode(4);
+    head.next = node2;
+    node2.next = node3;
+    node3.next = node4;
+    node4.next = node2;
+    assertTrue(LinkedListCycle.solution2(head));
+
+    head = new ListNode(1);
+    node2 = new ListNode(2);
+    head.next = node2;
+    node2.next = head;
+    assertTrue(LinkedListCycle.solution2(head));
+
+    head = new ListNode(1);
+    assertFalse(LinkedListCycle.solution2(head));
+  }
+}
