current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

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;
}
share|improve this question

migrated from stackoverflow.com Aug 7 '14 at 1:57

This question came from our site for professional and enthusiast programmers.
1  
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
1  
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

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
delnan, I appreciate your response, this enlightened me.. –  David Prun Aug 6 '14 at 8:09
1  
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
up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.