Skip to content

Commit 2e9e447

Browse files
parthkariaparthkaria
committed
Merge remote-tracking branch 'upstream/master'
Conflicts: libraries/pom.xml
2 parents 99e9e23 + d79fcae commit 2e9e447

652 files changed

Lines changed: 21652 additions & 1531 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎.gitignore‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,3 +41,5 @@ SpringDataInjectionDemo/.mvn/wrapper/maven-wrapper.properties
4141
spring-call-getters-using-reflection/.mvn/wrapper/maven-wrapper.properties
4242

4343
spring-check-if-a-property-is-null/.mvn/wrapper/maven-wrapper.properties
44+
*.springBeans
45+

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,4 +23,4 @@ Any IDE can be used to work with the projects, but if you're using Eclipse, cons
2323

2424
CI - Jenkins
2525
================================
26-
This tutorials project is being built **[>> HERE](https://rest-security.ci.cloudbees.com/job/tutorials/)**
26+
This tutorials project is being built **[>> HERE](https://rest-security.ci.cloudbees.com/job/github%20projects%20Jobs/job/tutorials/)**

‎algorithms/README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,3 +8,4 @@
88
- [Check If a Number Is Prime in Java](http://www.baeldung.com/java-prime-numbers)
99
- [Example of Hill Climbing Algorithm](http://www.baeldung.com/java-hill-climbing-algorithm)
1010
- [Monte Carlo Tree Search for Tic-Tac-Toe Game](http://www.baeldung.com/java-monte-carlo-tree-search)
11+
- [String Search Algorithms for Large Texts](http://www.baeldung.com/java-full-text-search-algorithms)

algorithms/src/main/java/com/baeldung/algorithms/BinarySearch.java renamed to algorithms/src/main/java/com/baeldung/algorithms/binarysearch/BinarySearch.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
package com.baeldung.algorithms.binarysearch;
2+
13
import java.util.Arrays;
24
import java.util.Collections;
35
import java.util.List;

‎algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionBruteForce.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.baeldung.algorithms.linkedlist;
2+
3+
public class CycleDetectionBruteForce {
4+
5+
public static <T> CycleDetectionResult<T> detectCycle(Node<T> head) {
6+
if (head == null) {
7+
return new CycleDetectionResult<>(false, null);
8+
}
9+
10+
Node<T> it1 = head;
11+
int nodesTraversedByOuter = 0;
12+
while (it1 != null && it1.next != null) {
13+
it1 = it1.next;
14+
nodesTraversedByOuter++;
15+
16+
int x = nodesTraversedByOuter;
17+
Node<T> it2 = head;
18+
int noOfTimesCurrentNodeVisited = 0;
19+
20+
while (x > 0) {
21+
it2 = it2.next;
22+
23+
if (it2 == it1) {
24+
noOfTimesCurrentNodeVisited++;
25+
}
26+
27+
if (noOfTimesCurrentNodeVisited == 2) {
28+
return new CycleDetectionResult<>(true, it1);
29+
}
30+
31+
x--;
32+
}
33+
}
34+
35+
return new CycleDetectionResult<>(false, null);
36+
}
37+
38+
}

‎algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionByFastAndSlowIterators.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package com.baeldung.algorithms.linkedlist;
2+
3+
public class CycleDetectionByFastAndSlowIterators {
4+
5+
public static <T> CycleDetectionResult<T> detectCycle(Node<T> head) {
6+
if (head == null) {
7+
return new CycleDetectionResult<>(false, null);
8+
}
9+
10+
Node<T> slow = head;
11+
Node<T> fast = head;
12+
13+
while (fast != null && fast.next != null) {
14+
slow = slow.next;
15+
fast = fast.next.next;
16+
17+
if (slow == fast) {
18+
return new CycleDetectionResult<>(true, fast);
19+
}
20+
}
21+
22+
return new CycleDetectionResult<>(false, null);
23+
}
24+
25+
}

‎algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionByHashing.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.baeldung.algorithms.linkedlist;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
public class CycleDetectionByHashing {
7+
8+
public static <T> CycleDetectionResult<T> detectCycle(Node<T> head) {
9+
if (head == null) {
10+
return new CycleDetectionResult<>(false, null);
11+
}
12+
13+
Set<Node<T>> set = new HashSet<>();
14+
Node<T> node = head;
15+
16+
while (node != null) {
17+
if (set.contains(node)) {
18+
return new CycleDetectionResult<>(true, node);
19+
}
20+
set.add(node);
21+
node = node.next;
22+
}
23+
24+
return new CycleDetectionResult<>(false, null);
25+
}
26+
27+
}

‎algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleDetectionResult.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package com.baeldung.algorithms.linkedlist;
2+
3+
public class CycleDetectionResult<T> {
4+
boolean cycleExists;
5+
Node<T> node;
6+
7+
public CycleDetectionResult(boolean cycleExists, Node<T> node) {
8+
super();
9+
this.cycleExists = cycleExists;
10+
this.node = node;
11+
}
12+
}

‎algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleRemovalBruteForce.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package com.baeldung.algorithms.linkedlist;
2+
3+
public class CycleRemovalBruteForce {
4+
5+
public static <T> boolean detectAndRemoveCycle(Node<T> head) {
6+
CycleDetectionResult<T> result = CycleDetectionByFastAndSlowIterators.detectCycle(head);
7+
8+
if (result.cycleExists) {
9+
removeCycle(result.node, head);
10+
}
11+
12+
return result.cycleExists;
13+
}
14+
15+
/**
16+
* @param loopNodeParam - reference to the node where Flyods cycle
17+
* finding algorithm ends, i.e. the fast and the slow iterators
18+
* meet.
19+
* @param head - reference to the head of the list
20+
*/
21+
private static <T> void removeCycle(Node<T> loopNodeParam, Node<T> head) {
22+
Node<T> it = head;
23+
24+
while (it != null) {
25+
if (isNodeReachableFromLoopNode(it, loopNodeParam)) {
26+
Node<T> loopStart = it;
27+
findEndNodeAndBreakCycle(loopStart);
28+
break;
29+
}
30+
it = it.next;
31+
}
32+
}
33+
34+
private static <T> boolean isNodeReachableFromLoopNode(Node<T> it, Node<T> loopNodeParam) {
35+
Node<T> loopNode = loopNodeParam;
36+
37+
do {
38+
if (it == loopNode) {
39+
return true;
40+
}
41+
loopNode = loopNode.next;
42+
} while (loopNode.next != loopNodeParam);
43+
44+
return false;
45+
}
46+
47+
private static <T> void findEndNodeAndBreakCycle(Node<T> loopStartParam) {
48+
Node<T> loopStart = loopStartParam;
49+
50+
while (loopStart.next != loopStartParam) {
51+
loopStart = loopStart.next;
52+
}
53+
54+
loopStart.next = null;
55+
}
56+
}

‎algorithms/src/main/java/com/baeldung/algorithms/linkedlist/CycleRemovalByCountingLoopNodes.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.baeldung.algorithms.linkedlist;
2+
3+
public class CycleRemovalByCountingLoopNodes {
4+
5+
public static <T> boolean detectAndRemoveCycle(Node<T> head) {
6+
CycleDetectionResult<T> result = CycleDetectionByFastAndSlowIterators.detectCycle(head);
7+
8+
if (result.cycleExists) {
9+
removeCycle(result.node, head);
10+
}
11+
12+
return result.cycleExists;
13+
}
14+
15+
private static <T> void removeCycle(Node<T> loopNodeParam, Node<T> head) {
16+
int cycleLength = calculateCycleLength(loopNodeParam);
17+
Node<T> cycleLengthAdvancedIterator = head;
18+
Node<T> it = head;
19+
20+
for (int i = 0; i < cycleLength; i++) {
21+
cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next;
22+
}
23+
24+
while (it.next != cycleLengthAdvancedIterator.next) {
25+
it = it.next;
26+
cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next;
27+
}
28+
29+
cycleLengthAdvancedIterator.next = null;
30+
}
31+
32+
private static <T> int calculateCycleLength(Node<T> loopNodeParam) {
33+
Node<T> loopNode = loopNodeParam;
34+
int length = 1;
35+
36+
while (loopNode.next != loopNodeParam) {
37+
length++;
38+
loopNode = loopNode.next;
39+
}
40+
41+
return length;
42+
}
43+
44+
}

0 commit comments

Comments
 (0)