利用节点地址在关联列表中进行循环检测。

Question

我最近了解到。

记忆中的堆总是向上生长的

---

参考-> https:/unix.stackexchange.comquestions466443do-memory-mapping-segment-and-heap-grow-until-they-meet-each-other。 我没有理解其中的大部分内容，但是当我搜索堆是否在内存中向上生长时，那么我得到了类似的结果。

考虑到以上事实，我在cc++中写了一个循环检测的函数，如果遍历指针到结构体的 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 ) (降序)，因为内存分配是devicecompiler特有的，但这也没有工作.我想知道为什么这段代码不能工作，这段代码有什么概念性错误。

Answer 1

如果你创建一个有几千个元素的链接列表，并试图计算下一个列表的地址比当前列表的地址小多少倍，你会得到几个，所以这种找天气有周期的方法是行不通的。正确的做法应该是做两个指针，其中一个指针一次移动一个列表，另一个指针一次移动两个列表，每次移动都要检查这两个指针的地址是否相同。

Answer 2

我不得不同意@gtristan的观点。我看不出内存地址的比较会导致一个明确的周期检测方案。一般的双节点方法是一个公认的解决方案，而且效果很好。看看这两个相关的周期检测算法。Floyd的龟兔赛跑算法 和 布伦特的伸缩龟算法. 我最近在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;
}

希望能帮到你...