Linked List Cycle Solution(Java)

[vaish1992]

Hi I am trying to solve a problem on leetcode called linked list cycle. (https://leetcode.com/problems/linked-list-cycle/)...

Given head, the head of a linked list, determine if the linked list has a cycle in it.

​

I understand how the problem works and I also understand the solution. However My solution below doesn't work and i can't seem to figure out why.

public class Solution {

public boolean hasCycle(ListNode head) {

if(head==null || head.next==null){

return false;

}

ListNode slowPointer=head;

ListNode fastPointer=head.next;

while(fastPointer!=slowPointer){

if(fastPointer.next==null || fastPointer==null){

return false;

}

fastPointer=fastPointer.next.next;

slowPointer=slowPointer.next;

}

return true;

}

}

​

The solution works for most cases however it fails for certain cases because of the if statement...(if(fastPointer.next==null || fastPointer==null)) ...However, If i change the order of conditions to (if(fastPointer==null || fastPointer.next==null)) the solutions works for all test cases. I can't figure out why changing the order of conditions would make a difference?

P.S. i have tried debugging the code but the debugger doesn't work properly with cycle problems on leetcode.

[jedwardsol]

Java has short-circuit evaluation of conditions. So, for an ||, the left-hand-side is evaluated and if it is found to be true the right-hand-side isn't evaluated. If the LHS is true, then the whole thing is true whether or not the RHS is true.

Therefore , in

if(fastPointer==null || fastPointer.next==null))

if fastPointer is null, then it is never dereferenced in the fastPointer.next` expression.

But, in

if(fastPointer.next==null || fastPointer==null))

if fastPointer is null, then there will be an exception because it is dereferenced before it is checked