Loop Detection - Cracking Coding Interview

http://umairsaeed.com/blog/2011/06/23/finding-the-start-of-a-loop-in-a-circular-linked-list/

Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

First, meeting point of two pointers in a loop

Consider two pointers: a slow pointer S that increments by one node at each step, and a fast pointer F that increments by two nodes at each step (i.e. it is twice as fast as S). Both pointers start at the same time from the beginning of an n-node loop. In the time S covers n nodes. Fwill have covered 2n nodes and they will both meet at the start of the loop.

Now, let us say that the slow pointer S starts at the beginning of the loop, and the fast pointer F starts at node k (where k < n) of the loop. As these two pointers move along the loop, they will meet at node (n-x).

What we really need to do is figure out x, as it will give us the node at which the two pointers meet inside the loop.

1. When S takes n/2 steps, it will be at node n/2. During the same time, F will have taken 2(n/2) = n steps, and it will be at node (k+n). Since the we are inside a loop, F will be effectively back at node k.
2. In order for the two pointers to meet at node (n-x), S needs to take a further (n-x-n/2)=(n/2-x) steps and it will end up at node n-x. During the same time, F will have taken 2*(n/2-x)=(n-2x) steps and will be at node k+(n-2x). Given our assumption that both S and F meet at the same node:

1 2	n-x = k+n-2x => x = k

This means that if S starts from the start of the loop, and F starts k nodes into the loop, both of them will meet at node (n-k), i.e k nodes from the end of the loop. This is a key insight.

public static IntegerNode findLoopStart(LinkedList linkedList) { if (linkedList == null || linkedList.getHead() == null) { return null; } IntegerNode loopStartNode = null; IntegerNode slow = linkedList.getHead(); IntegerNode fast = linkedList.getHead(); while (slow != null && fast != null) { slow = slow.getNext(); if (fast.getNext() == null) { loopStartNode = null; break; } fast = fast.getNext().getNext(); // If slow and fast point to the same node, it means that the // linkedList contains a loop. if (slow == fast) { slow = linkedList.getHead(); while (slow != fast) { // Keep incrementing the two pointers until they both // meet again. When this happens, both the pointers will // point to the beginning of the loop slow = slow.getNext(); // Can't be null, as we have a loop fast = fast.getNext(); // Can't be null, as we have a loop } loopStartNode = slow; break; } } return loopStartNode; }




public static boolean hasLoop(LinkedList linkedList) { if (linkedList == null || linkedList.getHead() == null) { return false; } IntegerNode slow = linkedList.getHead(); IntegerNode fast = linkedList.getHead(); while (true) { slow = slow.getNext(); if (fast.getNext() != null) { fast = fast.getNext().getNext(); } else { return false; } if (slow == null || fast == null) { return false; } if (slow == fast) { return true; } } }
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2002.%20Linked%20Lists/Q2_08_Loop_Detection/Question.java

public static LinkedListNode FindBeginning(LinkedListNode head) {
LinkedListNode slow = head;
LinkedListNode fast = head;

// Find meeting point
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}

// Error check - there is no meeting point, and therefore no loop
if (fast == null || fast.next == null) {
return null;
}

/* Move slow to Head. Keep fast at Meeting Point. Each are k steps
/* from the Loop Start. If they move at the same pace, they must
* meet at Loop Start. */
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}

// Both now point to the start of the loop.
return fast;
}

http://javabypatel.blogspot.in/2015/12/detect-loop-in-linked-list.html

Why increase pointer by two while finding loop in linked list, why not 3,4,5?

So, the condition here is you cannot change the speed of ptr1, it has to move one node at a time. 
but the choice for ptr2 to move can be 2 nodes at a time, 3 nodes at a time or any number of nodes at a time. 

More the gap in which both pointers move forward, more the time they might take in worst case to meet. 
So the lowest possible iteration in which we can find their meeting points is by moving ptr2 two nodes at a time.
http://www.geeksforgeeks.org/detect-and-remove-loop-in-a-linked-list/