0

我最近了解到：

（通常）内存中的堆总是向上增长

参考-> https://unix.stackexchange.com/questions/466443/do-memory-mapping-segment-and-heap-grow-until-they-meet-each-other
我大部分都不懂，但是当我搜索堆是否在内存中向上增长时，我得到了类似的结果。

考虑到 c/c++ 中的上述事实，我编写了一个检查循环检测的函数，如果指向结构的遍历指针指向temp的内存地址小于链表中前一个节点的内存地址，则该函数返回 TRUE 以进行循环检测.

不幸的是，下面的代码在hackerrank上没有给出预期的结果，我想知道为什么。代码是：

bool has_cycle(SinglyLinkedListNode* head) {
    struct SinglyLinkedListNode* temp = head;
    int x;
    if( temp == NULL )
    return false;             //FALSE indicates No cycle detected in linked list

    if( temp->next == NULL )
    return false;

    x = temp;
    while( temp->next != NULL )
    {
        temp = temp->next;
        if( x >= temp )
        return true;          //TRUE indicates Cycle detected in linked list

        x= temp;
    }

    return false;

}

我已经检查了堆中的内存分配是否向下if( x <= temp )（降序）的条件，因为内存分配是特定于设备/编译器的，但这也不起作用。我想知道为什么这段代码不起作用以及这段代码存在哪些概念错误。

4

2 回答 2

1

如果你创建一个包含数千个元素的链表并尝试计算下一个列表的地址比当前的地址小多少倍，你会得到一些，所以这种查找天气有循环的方法不会工作。正确的方法是创建两个指针，其中一个将一次移动一个列表，另一个将一次移动两个列表，并检查每个移动是否这两个指针的地址相同。

于 2020-05-16T20:24:24.140 回答
0

我必须同意@gtristan。我看不到内存地址比较将导致确定的周期检测解决方案的位置。一般的两节点方法是一种公认​​的解决方案并且效果很好。看看这两个相关的循环检测算法：Floyd 的 Tortoise And Hare 算法和Brent 的 Telescoping Turtle 算法。我最近在 HackerRank 上用 Java 实现了 Floyd 算法（下面没有花哨的代码），并且在所有测试用例中运行干净：

// Complete the hasCycle function below.
/*
 * For your reference:
 *
 * SinglyLinkedListNode {
 *     int data;
 *     SinglyLinkedListNode next;
 * }
 *
 */
static boolean hasCycle(SinglyLinkedListNode head) {
    if (head == null) { return false; }
    SinglyLinkedListNode slow = head, fast = head;
    while (slow.next != null) {
        slow = slow.next;
        if (fast.next != null) {
            fast = fast.next;
            if (fast.next != null) {
                fast = fast.next;
                if (fast == slow) {
                    return true;
                }
            }
        }
    }
    return false;
}

希望这可以帮助 -

于 2020-05-16T20:59:07.260 回答