Finding a Cycle in a Linked List

Question

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.

Answer 1

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.

• Ramkrishna Sharma: Hey - thanks for your response! I guess the take-away argument here is that I should check if fast.next.next actually exists before doing fast = fast.next.next ... so, I could try doing if(fast.next.next != null) { fast = fast.next.next; } ... however, you're advising me to check if fast.next != null instead of fast.next.next != null.. If I were at the second to last node, then fast.next may very well exist, but fast.next.next would not, leaving me with same null-pointer exception.. thoughts?
• Stephen C: I am advising that you need to test fast AND fast.next. You don't need to check fast.next.next because that will be tested in the following loop iteration ... after fast has been assigned the value of fast.next.next. My advice is to stop asking us to explain. Go get a piece of paper and a pencil and hand execute the code until you understand what is going on.

Answer 2

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.

Answer 3

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.

• Ramkrishna Sharma: Hey - thanks for your response! I guess the take-away argument here is that I should check if fast.next.next actually exists before doing fast = fast.next.next ... so, I could try doing if(fast.next.next != null) { fast = fast.next.next; } ... however, you're advising me to check if fast.next != null instead of fast.next.next != null.. If I were at the second to last node, then fast.next may very well exist, but fast.next.next would not, leaving me with same null-pointer exception.. thoughts?
• Mayank Narula: you should check for fast && fast.next and you shall never encounter NULL pointer exception. Try doing a dry run for number of nodes both even and odd say 6 and 7.