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?

I don't see how. On the first loop it checks `head.next` which is 2 and `head.next.next` which is 3. — c0der, Jul 10 '18 at 04:57
@c0der If the list is `1, 2, 3, 4` and the loop is between `3` and `4`, you'll end up iterating like `1, 1`, `2, 3`, `3, 3`, because at that point the `.next.next` of `3` is still `3`. — ChatterOne, Jul 10 '18 at 07:06

Anatolii · Accepted Answer · 2020-01-05T10:38:10.327

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.

score 1 · Answer 2 · edited Sep 30 '18 at 16:04

1

Tests of this challenge are incorrect, and there are no loops. Check it by printing out head.next....next. You can get NPE where tests waiting for return TRUE. See linked lists generations in other languages.

edited Sep 30 '18 at 16:04

Anatolii

14,139
4
35
65

answered Sep 24 '18 at 18:29

Alex T.

29
4

Cycle detection in java

2 Answers2

UPDATE