C语言 使用节点地址在链表中进行周期检测

Question

我最近了解到：

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

---

参考->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 )(降序(的条件，因为内存分配特定于设备/编译器，但这也不起作用。 我想知道为什么这段代码不起作用以及这段代码包含哪些概念错误。

Answer 1

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

Answer 2

我必须同意@gtristan。我看不出内存地址比较将在哪里导致明确的循环检测解决方案。一般的双节点方法是公认的解决方案，并且效果很好。看看这两个相关的周期检测算法：弗洛伊德的龟兔算法和布伦特的伸缩海龟算法。我最近在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;
}

希望这有帮助——