Cycle detection in java

Question

I'm working on a hackerrank problem and it seems like no matter the variation of the solution I try, I can't get the cycle detection to work.

Here's the code I'm using

static boolean hasCycle(SinglyLinkedListNode head) {
        if (head == null) return false;

        SinglyLinkedListNode slow, fast;
        slow = head;
        fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

I can tweak the solution to get the other test to pass, but not both. In this case true is never returned, even when it should be. How can I fix this, what am I doing wrong?

Answer 1

It has to do with Hackerrank itself. I tried my own solution that passed all the tests some time ago but it also failed for cases where there were cycles. So, I took a look at Hackerrank's insertNode method used for creating lists in test cases:

public void insertNode(int nodeData) {
    // here a new node object is created each time a method is called
    SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);

    if (this.head == null) {
        this.head = node;
    } else {
        this.tail.next = node;
    }

    this.tail = node;
}

And then how it's used in their main:

public static void main(String[] args) throws IOException {
    BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    int tests = scanner.nextInt();
    scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

    for (int testsItr = 0; testsItr < tests; testsItr++) {
        int index = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        SinglyLinkedList llist = new SinglyLinkedList();

        int llistCount = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < llistCount; i++) {
            int llistItem = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            // a new node is inserted each time so no cycle can be created whatsoever.
            llist.insertNode(llistItem);
        }

        boolean result = hasCycle(llist.head);

        bufferedWriter.write(String.valueOf(result ? 1 : 0));
        bufferedWriter.newLine();
    }

    bufferedWriter.close();

    scanner.close();
}

As you can see for each llistItem value llist.insertNode(llistItem) is invoked to add an item to the list. This method, however, can't create cycles as it creates a new SinglyLinkedListNode each time. So, even though some llistItem values are the same the nodes containing them are always different.

UPDATE

As of January 5, 2020, Hackerrank tests are fixed and the solution provided by the OP passes all of them.