BAEL-1123 - Testing Linked List for Cycles - deep20jain@gmail.com (eugenp#2525)

deep20jain · zhendrikse · commit d8398caaa2d8 · 2017-09-03T22:20:25.000+02:00
* Adding node and cycle detection by hashing

* Adding implementation for all algorithms for cycle detection and removal

* Applying formatting rules
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionBruteForce.java b/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionBruteForce.java
@@ -0,0 +1,38 @@
+package com.baeldung.algorithms.linkedlist;
+
+public class CycleDetectionBruteForce {
+
+    public static <T> boolean detectCycle(Node<T> head) {
+        if (head == null) {
+            return false;
+        }
+
+        Node<T> it1 = head;
+        int nodesTraversedByOuter = 0;
+        while (it1 != null && it1.next != null) {
+            it1 = it1.next;
+            nodesTraversedByOuter++;
+
+            int x = nodesTraversedByOuter;
+            Node<T> it2 = head;
+            int noOfTimesCurrentNodeVisited = 0;
+
+            while (x > 0) {
+                it2 = it2.next;
+
+                if (it2 == it1) {
+                    noOfTimesCurrentNodeVisited++;
+                }
+
+                if (noOfTimesCurrentNodeVisited == 2) {
+                    return true;
+                }
+
+                x--;
+            }
+        }
+
+        return false;
+    }
+
+}
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionByFastAndSlowIterators.java b/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionByFastAndSlowIterators.java
@@ -0,0 +1,25 @@
+package com.baeldung.algorithms.linkedlist;
+
+public class CycleDetectionByFastAndSlowIterators {
+
+    public static <T> boolean detectCycle(Node<T> head) {
+        if (head == null) {
+            return false;
+        }
+
+        Node<T> slow = head;
+        Node<T> fast = head;
+
+        while (fast != null && fast.next != null) {
+            slow = slow.next;
+            fast = fast.next.next;
+
+            if (slow == fast) {
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+}
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionByHashing.java b/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionByHashing.java
@@ -0,0 +1,27 @@
+package com.baeldung.algorithms.linkedlist;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public class CycleDetectionByHashing {
+
+    public static <T> boolean detectCycle(Node<T> head) {
+        if (head == null) {
+            return false;
+        }
+
+        Set<Node<T>> set = new HashSet<>();
+        Node<T> node = head;
+
+        while (node != null) {
+            if (set.contains(node)) {
+                return true;
+            }
+            set.add(node);
+            node = node.next;
+        }
+
+        return false;
+    }
+
+}
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleRemovalBruteForce.java b/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleRemovalBruteForce.java
@@ -0,0 +1,61 @@
+package com.baeldung.algorithms.linkedlist;
+
+public class CycleRemovalBruteForce {
+
+    public static <T> boolean detectAndRemoveCycle(Node<T> head) {
+        if (head == null) {
+            return false;
+        }
+
+        Node<T> slow = head;
+        Node<T> fast = head;
+
+        while (fast != null && fast.next != null) {
+            slow = slow.next;
+            fast = fast.next.next;
+
+            if (slow == fast) {
+                removeCycle(slow, head);
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    private static <T> void removeCycle(Node<T> loopNodeParam, Node<T> head) {
+        Node<T> it = head;
+
+        while (it != null) {
+            if (isNodeReachableFromLoopNode(it, loopNodeParam)) {
+                Node<T> loopStart = it;
+                findEndNodeAndBreakCycle(loopStart);
+                break;
+            }
+            it = it.next;
+        }
+    }
+
+    private static <T> boolean isNodeReachableFromLoopNode(Node<T> it, Node<T> loopNodeParam) {
+        Node<T> loopNode = loopNodeParam;
+
+        while (loopNode.next != loopNodeParam) {
+            if (it == loopNode) {
+                return true;
+            }
+            loopNode = loopNode.next;
+        }
+
+        return false;
+    }
+
+    private static <T> void findEndNodeAndBreakCycle(Node<T> loopStartParam) {
+        Node<T> loopStart = loopStartParam;
+
+        while (loopStart.next != loopStartParam) {
+            loopStart = loopStart.next;
+        }
+
+        loopStart.next = null;
+    }
+}
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleRemovalByCountingLoopNodes.java b/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleRemovalByCountingLoopNodes.java
@@ -0,0 +1,55 @@
+package com.baeldung.algorithms.linkedlist;
+
+public class CycleRemovalByCountingLoopNodes {
+
+    public static <T> boolean detectAndRemoveCycle(Node<T> head) {
+        if (head == null) {
+            return false;
+        }
+
+        Node<T> slow = head;
+        Node<T> fast = head;
+
+        while (fast != null && fast.next != null) {
+            slow = slow.next;
+            fast = fast.next.next;
+
+            if (slow == fast) {
+                int cycleLength = calculateCycleLength(slow);
+                removeCycle(head, cycleLength);
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    private static <T> void removeCycle(Node<T> head, int cycleLength) {
+        Node<T> cycleLengthAdvancedIterator = head;
+        Node<T> it = head;
+
+        for (int i = 0; i < cycleLength; i++) {
+            cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next;
+        }
+
+        while (it.next != cycleLengthAdvancedIterator.next) {
+            it = it.next;
+            cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next;
+        }
+
+        cycleLengthAdvancedIterator.next = null;
+    }
+
+    private static <T> int calculateCycleLength(Node<T> loopNodeParam) {
+        Node<T> loopNode = loopNodeParam;
+        int length = 1;
+
+        while (loopNode.next != loopNodeParam) {
+            length++;
+            loopNode = loopNode.next;
+        }
+
+        return length;
+    }
+
+}
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleRemovalWithoutCountingLoopNodes.java b/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleRemovalWithoutCountingLoopNodes.java
@@ -0,0 +1,38 @@
+package com.baeldung.algorithms.linkedlist;
+
+public class CycleRemovalWithoutCountingLoopNodes {
+
+    public static <T> boolean detectAndRemoveCycle(Node<T> head) {
+        if (head == null) {
+            return false;
+        }
+
+        Node<T> slow = head;
+        Node<T> fast = head;
+
+        while (fast != null && fast.next != null) {
+            slow = slow.next;
+            fast = fast.next.next;
+
+            if (slow == fast) {
+                removeCycle(slow, head);
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    private static <T> void removeCycle(Node<T> meetingPointParam, Node<T> head) {
+        Node<T> loopNode = meetingPointParam;
+        Node<T> it = head;
+
+        while (loopNode.next != it.next) {
+            it = it.next;
+            loopNode = loopNode.next;
+        }
+
+        loopNode.next = null;
+    }
+
+}
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/Node.java b/algorithms/src/main/java/com/baeldung/algorithms/linkedlist/Node.java
@@ -0,0 +1,38 @@
+package com.baeldung.algorithms.linkedlist;
+
+public class Node<T> {
+    T data;
+    Node<T> next;
+
+    public static <T> Node<T> createNewNode(T data, Node<T> next) {
+        Node<T> node = new Node<T>();
+        node.data = data;
+        node.next = next;
+        return node;
+    }
+
+    public static <T> void traverseList(Node<T> root) {
+        if (root == null) {
+            return;
+        }
+
+        Node<T> node = root;
+        while (node != null) {
+            System.out.println(node.data);
+            node = node.next;
+        }
+    }
+
+    public static <T> Node<T> getTail(Node<T> root) {
+        if (root == null) {
+            return null;
+        }
+
+        Node<T> node = root;
+        while (node.next != null) {
+            node = node.next;
+        }
+        return node;
+    }
+
+}
diff --git a/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleDetectionBruteForceTest.java b/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleDetectionBruteForceTest.java
@@ -0,0 +1,20 @@
+package com.baeldung.algorithms.linkedlist;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class CycleDetectionBruteForceTest extends CycleDetectionTestBase {
+
+    @Test
+    public void givenNormalList_dontDetectLoop() {
+        Node<Integer> root = createList();
+        Assert.assertFalse(CycleDetectionBruteForce.detectCycle(root));
+    }
+
+    @Test
+    public void givenCyclicList_detectLoop() {
+        Node<Integer> root = createList();
+        createLoop(root);
+        Assert.assertTrue(CycleDetectionBruteForce.detectCycle(root));
+    }
+}
diff --git a/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleDetectionByFastAndSlowIteratorsTest.java b/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleDetectionByFastAndSlowIteratorsTest.java
@@ -0,0 +1,20 @@
+package com.baeldung.algorithms.linkedlist;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class CycleDetectionByFastAndSlowIteratorsTest extends CycleDetectionTestBase {
+
+    @Test
+    public void givenNormalList_dontDetectLoop() {
+        Node<Integer> root = createList();
+        Assert.assertFalse(CycleDetectionByFastAndSlowIterators.detectCycle(root));
+    }
+
+    @Test
+    public void givenCyclicList_detectLoop() {
+        Node<Integer> root = createList();
+        createLoop(root);
+        Assert.assertTrue(CycleDetectionByFastAndSlowIterators.detectCycle(root));
+    }
+}
diff --git a/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleDetectionByHashingTest.java b/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleDetectionByHashingTest.java
@@ -0,0 +1,20 @@
+package com.baeldung.algorithms.linkedlist;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class CycleDetectionByHashingTest extends CycleDetectionTestBase {
+
+    @Test
+    public void givenNormalList_dontDetectLoop() {
+        Node<Integer> root = createList();
+        Assert.assertFalse(CycleDetectionByHashing.detectCycle(root));
+    }
+
+    @Test
+    public void givenCyclicList_detectLoop() {
+        Node<Integer> root = createList();
+        createLoop(root);
+        Assert.assertTrue(CycleDetectionByHashing.detectCycle(root));
+    }
+}
diff --git a/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleDetectionTestBase.java b/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleDetectionTestBase.java
@@ -0,0 +1,27 @@
+package com.baeldung.algorithms.linkedlist;
+
+public class CycleDetectionTestBase {
+
+    public static Node<Integer> createList() {
+        Node<Integer> root = Node.createNewNode(10, null);
+
+        for (int i = 9; i >= 1; --i) {
+            Node<Integer> current = Node.createNewNode(i, root);
+            root = current;
+        }
+
+        return root;
+    }
+
+    public static void createLoop(Node<Integer> root) {
+        Node<Integer> tail = Node.getTail(root);
+
+        Node<Integer> middle = root;
+        for (int i = 1; i <= 4; i++) {
+            middle = middle.next;
+        }
+
+        tail.next = middle;
+    }
+
+}
diff --git a/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleRemovalBruteForceTest.java b/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleRemovalBruteForceTest.java
diff --git a/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleRemovalByCountingLoopNodesTest.java b/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleRemovalByCountingLoopNodesTest.java
diff --git a/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleRemovalWithoutCountingLoopNodesTest.java b/algorithms/src/test/java/com/baeldung/algorithms/linkedlist/CycleRemovalWithoutCountingLoopNodesTest.java
