java 中的循环检测

Question

我正在研究 hackerrank problem，似乎无论我尝试的解决方案如何变化，我都无法使循环检测工作。

这是我正在使用的代码

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;
    }

我可以调整解决方案以使另一个测试通过，但不能同时通过。在这种情况下，永远不会返回 true，即使它应该返回。我该如何解决这个问题，我做错了什么？

Answer 1

它与 Hackerrank 本身有关。我尝试了我自己的解决方案，该解决方案前段时间通过了所有测试，但在存在循环的情况下也失败了。因此，我查看了 Hackerrank 的 insertNode 用于在测试用例中创建列表的方法：

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;
}

然后是如何在他们的 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();
}

如您所见，对每个 llistItem 值调用 llist.insertNode(llistItem) 以将项目添加到列表中。但是，此方法无法创建循环，因为它每次都会创建一个 new SinglyLinkedListNode。因此，即使某些 llistItem 值相同，包含它们的节点也总是不同的。

更新

截至 2020 年 1 月 5 日，Hackerrank 测试已修复，OP 提供的解决方案通过了所有测试。

Answer 2

这个挑战的测试不正确，没有循环。通过打印 head.next... 来检查它。接下来。您可以在等待 return TRUE 的测试中获得 NPE。查看其他语言的链表生成。

java 中的循环检测

Cycle detection in java

java

algorithm

cycle-detection

更新