CODEWITHSUNDEEP
javaalgorithmlinked-listcycle-detection
Dulen De Silva
Dulen De Silva

Reputation: 1

How to detect a cycle in a Singly Linked List in Java?

I am trying to detect if a Singly Linked List has a cycle (loop) in Java. I have attempted to use Floyd’s Cycle Detection Algorithm (Tortoise and Hare Algorithm), but my implementation does not work correctly.

What is wrong with my implementation?

Here is my code:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListCycleDetection {
    public static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null || fast.next != null) {  
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true; 
            }
        }
        return false; 
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = head.next; 

        System.out.println(hasCycle(head)); 
    }
}

References I’ve consulted:

GeeksforGeeks - Detect Loop in Linked List

Upvotes: -7

Views: 108

Answers (1)

Psv Varshan
Psv Varshan

Reputation: 1

The use of || operator (the or operator) in the while loop is the first thing you have to focus on. The or operator is usually quoted as "Hunter for Truth" where in this case you have high chances of getting null.pointerException that occurs when you try to access null values. For example imagine you have 4 values that aren't cyclic. Since this is a boolean Function and it works on by returning true or false. The only input you have given is a cyclic LinkedList that typically doesn't hold any null value. Try giving it a Singly LinkedList without any cyclic properties and you will eventually realize that there is an error because the while loop there will also run if one or more conditions satisfy in or operator. Here if fast.next is not null and fast.next.next is null then it will be returning error for a normal linkedList because there is definitely a null at the tail of LinkedList. It is advisory to use your code as while

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

since and operator will only make this while loop run if and only if both the conditions are satisfied.

Hope it helps

Upvotes: 0

Related Questions