CODEWITHSUNDEEP
javaalgorithmdata-structureslinked-listfloyd-cycle-finding
Ramkrishna Sharma
Ramkrishna Sharma

Reputation: 1

Finding a Cycle in a Linked List

I'm currently working with Floyd's Cycle Finding Algorithm for a question that asks me to detect if a singly linked list contains a cycle.. I understand the Tortoise and Hare approach but am somewhat confused regarding its implementation. There have been several posts about this algorithm but never that targets this aspect of the question.

public class Solution {
public boolean hasCycle(ListNode head) {
    
    ListNode slow = head;
    ListNode fast = head; 
    
    while(fast != null) {
        fast = fast.next.next; 
        slow = slow.next; 
        
        if(fast == slow)
            return true; 
    }
    return false;   
}

The only error in my code is that in my while-loop condition, I should have

while(fast != null && fast.next != null)

Instead of..

while(fast != null)

however, the latter while-loop condition makes more sense to me. I acknowledge that the correct implementation is simply assessing whether a particular node exists, and whether or not that node has a successor. However, if we simply check for while(fast != null) - wouldn't that suffice? After all, if fast = null, why bother to check fast.next anyways? Could there ever be a case where fast = null and a cycle exists? No, right? The standard implementation to judge whether we've reached the end of a linked list is: while(current != null) - why can't we do that here?

Thanks in advance.

Upvotes: 0

Views: 392

Answers (3)

Mayank Narula
Mayank Narula

Reputation: 409

Try a dry run of your code with odd number of elements say 5 and no cycle.

Observe what happens when fast reaches the end of the list.

Upvotes: 0

Sharad Nanda
Sharad Nanda

Reputation: 502

You have the fast = fast.next.next; for which you need to have the null check of fast.next otherwise your code can throw null pointer exception.

You can change

fast = fast.next.next;

to

if(fast.next != null) fast = fast.next.next;
else break;

You can avoid an extra line of code by keeping this check at the loop entry itself.

Upvotes: 0

Stephen C
Stephen C

Reputation: 719576

However, if we simply check for while(fast != null) - wouldn't that suffice?

No.

If you don't check that fast.next is not null, then when you do fast.next.next, you could get a NullPointerException.

(It depends on whether the number of elements in a cycle-free list is odd or even.)

Of course, you could move the fast.next != null into the loop ... but that is just rearranging the code. The effect will be the same.

Upvotes: 2

Related Questions