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

DEFINITION

Circular linked list:

A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

EXAMPLE

input: A -> B -> C -> D -> E -> C [the same C as earlier]

output: C

**My initial thoughts:**

Initialize with two pointers to the head, the slow pointer and fast pointer. Each time, slow pointer moves one step while the fast pointer moves two steps. If they meet in the some point, then that node must be the starting point of the loop.

**My initial codes:**

public static LLNode findLoopBeginningPoint(
LLNode head) {
LLNode slowPointer = head;
LLNode fastPointer = head;
fastPointer = fastPointer.getNext();
fastPointer = fastPointer.getNext();
while (slowPointer != fastPointer) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext();
fastPointer = fastPointer.getNext();
}
return slowPointer;
}

**Comments after running:**

The testing input yields out ‘E’ instead of the expected result ‘C’. Walk through the code:

- fastPointer: ‘C’; slowPointer: ‘A’
- fastPointer: ‘E’; slowPointer: ‘B’
- fastPointer: ‘D’; slowPointer: ‘C’
- fastPointer: ‘C’; slowPointer: ‘D’
- fastPointer: ‘E’; slowPointer: ‘E’

The catch point of this algorithm is that when the fast pointer meets the slow pointer, the distance between their meeting point and the starting point of the loop, is equal to the distance between the head of the list and the starting point of the loop.

Let us denote the length of non-loop list as , i.e., the distance between the head of the list to the starting point of the loop is . Let’s also have the size of the loop as . When the two pointer meets, let us denote the distance between the meeting point of the starting of the loop as . So, at the time of their meet, the fast pointer would have travelled and the slow pointer only travelled . Therefore we have .

Therefore, when the two pointer meets, we can move one pointer to the head, and then move them one step at each time, when they meet again, they will meet at the starting pointer of the loop.

public static LLNode<Character> findLoopBeginningPoint(
LLNode<Character> head) {
LLNode<Character> slowPointer = head;
LLNode<Character> fastPointer = head;
do {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext().getNext();
} while (slowPointer != fastPointer);
if (slowPointer == null)
return null;
slowPointer = head;
while (slowPointer != fastPointer) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext();
}
return slowPointer;
}

**Comments after running**

If the linked list has no loop, the highlighted line will raise an null-pointer exception under some circumstances.

**Solution**

public static LLNode<Character> FindBeginning(LLNode<Character> head) {
LLNode<Character> n1 = head;
LLNode<Character> n2 = head;
// find meeting point
while (n2.getNext() != null) {
n1 = n1.getNext();
n2 = n2.getNext().getNext();
if (n1 == n2)
break;
}
// Error check - there is no meeting point, and therefore no loop
if (n2.getNext() == null)
return null;
/*
* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps from the
* Loop Start. If they move at the same pace, they must meet at Loop
* Start.
*/
n1 = head;
while (n1 != n2) {
n1 = n1.getNext();
n2 = n2.getNext();
}
return n2;
}