Date: May 8, 2016

Floyd's Cycle Detection Algorithm (The Tortoise and The Hare) and Brent's Cycle Detection Algorithm (The Teleporting Turtle) are two famous algorithms that solve this problem. Both make use of two pointers that travel through the list at different speeds. If there is a loop/cycle, then the faster moving pointer (the hare) will eventually lap the slower moving pointer (the tortoise). Therefore, when both the hare and the tortoise point to the same node, then a loop/cycle has been detected. Otherwise, if the hare reaches the end of the list, then there is no loop/cycle.

With Floyd's Cycle Detection Algorithm, the hare takes two steps for every step that the tortoise takes. In Brent's Cycle Detection Algorithm, the tortoise stays stationary until the rabbit has taken 2^{n} steps at which time the tortoise teleports to the hare's position and the step counter is reset. The value of n starts at 1 and increases by 1 at each teleportation. Both algorithms have a linear O(n) time complexity, but Brent's algorithm is faster on average.

To find the start of the cycle when it has been detected, move the tortoise to the start of the list and increment both the tortoise and the hare one step at a time. The node that they meet at is the start of the cycle.

With Floyd's Cycle Detection Algorithm, the hare takes two steps for every step that the tortoise takes. In Brent's Cycle Detection Algorithm, the tortoise stays stationary until the rabbit has taken 2

To find the start of the cycle when it has been detected, move the tortoise to the start of the list and increment both the tortoise and the hare one step at a time. The node that they meet at is the start of the cycle.

public boolean detectCycleFloyd() { Node tortoise = head; Node hare = head; while (true) { if (hare == null) { return false; } hare = hare.next; if (hare == null) { return false; } hare = hare.next; tortoise = tortoise.next; if (tortoise == hare) { findCycleStart(hare, tortoise); return true; } } } public boolean detectCycleBrent() { Node tortoise = head; Node hare = head; int stepMax = 2; int count = 0; while (true) { if (hare == null) { return false; } hare = hare.next; count++; if (hare == tortoise) { findCycleStart(hare, tortoise); return true; } if (count == stepMax) { count = 0; stepMax *= 2; tortoise = hare; } } } public void findCycleStart(Node hare, Node tortoise) { tortoise = head; while (true) { if (tortoise == hare) { System.out.println("Start: " + hare.value); break; } tortoise = tortoise.next; hare = hare.next; } }

▸ Shuffling

▸ 3-Way Partition Quicksort

▸ Dual-Pivot Quicksort

▸ Quicksort

▸ Implement Stack using Two Queues

▸ Heapsort

▸ Merge Sort

▸ The Tower of Hanoi

▸ Shell Sort

▸ Selection Sort

▸ Insertion Sort

▸ Bubble Sort

▸ Finding the Maximum Submatrix

▸ Finding the Maximum Subarray

▸ Determining if a Tree is Symmetric

▸ Determining if Two Trees are Identical

▸ Stock Profit using Greedy Algorithm

▸ Generating Prime Numbers

▸ Calculate a Fibonacci Number

▸ Determine if a String is a Palindrome

▸ Find the Factorial of a Number

▸ Tree Traversal

▸ Swap Numbers Without Temp Variable

▸ Generating All Permutations of a String

▸ Binary Search Algorithm

▸ Reversing the Words in a String

▸ Checking if a Point Lies Within a Polygon

▸ Checking Array for Duplicate Elements

▸ Detecting a Loop in Singly Linked List

▸ Remove Node at Position in Linked List

▸ Reversing a Singly Linked List

▸ Extract n Bits Between Bits i and j

▸ Isolate Last Bit

▸ Unset Last Bit

▸ 3-Way Partition Quicksort

▸ Dual-Pivot Quicksort

▸ Quicksort

▸ Implement Stack using Two Queues

▸ Heapsort

▸ Merge Sort

▸ The Tower of Hanoi

▸ Shell Sort

▸ Selection Sort

▸ Insertion Sort

▸ Bubble Sort

▸ Finding the Maximum Submatrix

▸ Finding the Maximum Subarray

▸ Determining if a Tree is Symmetric

▸ Determining if Two Trees are Identical

▸ Stock Profit using Greedy Algorithm

▸ Generating Prime Numbers

▸ Calculate a Fibonacci Number

▸ Determine if a String is a Palindrome

▸ Find the Factorial of a Number

▸ Tree Traversal

▸ Swap Numbers Without Temp Variable

▸ Generating All Permutations of a String

▸ Binary Search Algorithm

▸ Reversing the Words in a String

▸ Checking if a Point Lies Within a Polygon

▸ Checking Array for Duplicate Elements

▸ Detecting a Loop in Singly Linked List

▸ Remove Node at Position in Linked List

▸ Reversing a Singly Linked List

▸ Extract n Bits Between Bits i and j

▸ Isolate Last Bit

▸ Unset Last Bit