# Is this circular linked list better than the fast & slow pointer method?

I have a faster way to find if a list is circular linked list, in contrast to the solution that Cracking the Coding Interview has offered:

In the below algorithm, fast-pointer will either hit null (in case of linear list) or hit starting point/origin (in case of circular) quicker than conventional (fast & slow pointer approach).

Reason: because in fast & slow pointer approach, we wait for the fastPointer == slowPointer condition to determine if it's a circular list. But fastPointer would reach its origin/starting point first before hitting slow pointer. (what's the point of crossing over the starting point and continuing the hunt for slowPointer?)

Isn't the below example a better algorithm? If so, then why have a fast & slow pointer approach?

(I didn't consider starting point as "node outside of loop" scenario while asking question.)

public boolean findCircular(Node someRandomNodeOfList) {

Node fast = someRandomNodeOfList;
while (true) {
if ((fast.next == null) || (fast.next.next == null)) {
return false;
}
else if (fast.next == someRandomNodeOfList|| fast.next.next == someRandomNodeOfList) {
return true;
}
else {
fast = fast.next.next;
}
}
return false;
}

• I think you're making a faulty assumption: that the circular portion of a looped linked list includes the list's head. – kviiri Aug 6 '14 at 7:57
• Even if its not a head, I would store starting point as say root. and then if I reach my starting point I conclude it is circular list.. right? – David Prun Aug 6 '14 at 8:00
• if loop in list starts from 3 nodes away from the roor then your algo don't work. you are checking with root node only. if loop in list include root node then it is fine otherwise not. – hcl Aug 6 '14 at 8:00
• I corrected my code for better way of presenting question. thanks. – David Prun Aug 6 '14 at 8:03
• If you wanted speed, you would use an array as a circular buffer and this problem would be trivial. Note: this is how network adapters work. It's a bit like saying, how can I make this slow thing a bit faster without using the proper data structure for this problem. – Peter Lawrey Aug 6 '14 at 8:12

This works when you're starting from inside the cycle. However, the following is also a valid circular list:

N1 --> N2 --> N3 --> N4
^             v
+-------------+


Your algorithm works when starting from N2, N3 or N4, but not when starting from N1.

• delnan, I appreciate your response, this enlightened me.. – David Prun Aug 6 '14 at 8:09
• I think delnan is right. @DavidPrun You always checking against the same "someRandomNodeOfList". If the "someRandomNodeOfList" is out of the circle then you will end up in a infinite loop without finding an answer. For more info refer this. en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare – naveejr Aug 6 '14 at 8:17

## Failure to solve the challenge

The problem in Cracking the Coding Interview asks to find not only whether the list contains a cycle, but where the cycle begins.

## Failure to compile

Since while (true) { … } is an infinite loop, the while true; at the end is unreachable code, which is a compilation error in Java.

Since while (true) is always a kind of a lie, it would have been better to rewrite the loop as:

while (fast.next != null && fast.next.next != null) {
if (fast.next == someRandomNodeOfList || fast.next.next == someRandomNodeOfList) {
return true;
}
fast = fast.next.next;
}
return false;


## Why unroll the loop?

Advancing two links at a time (fast = fast.next.next;) is unconventional. What you are really doing is performing the work of two conventional loop iterations in one iteration. The normal way to write that is much easier to understand:

for (Node fast = someRandomNodeOfList; fast.next != null; fast = fast.next) {
if (fast.next == someRandomNodeOfList) {
return true;
}
}
return false;


Perhaps that formulation makes it easier to see the bug that @delnan spotted.