LeetCode 142题：错误的链表环检测代码为何能运行？

问题背景 #

我在LeetCode上写了一段逻辑错误的链表环检测代码，明明不符合通用的环检测逻辑，但它却能在LeetCode的测试用例中正常运行。正确的环检测解法应该是快慢指针法，现在想搞清楚两个问题：

1. 错误代码能运行的原因是什么？
2. 为什么LeetCode中链表节点的malloc地址总是呈现后分配的节点地址比前一个大的规律？

错误代码 #

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *cur = head;

    while(cur){
        if(cur >= cur->next) return cur->next;
        
        cur = cur->next;
    }
    return NULL;
}

正确解法（快慢指针法） #

struct ListNode *detectCycle(struct ListNode *head) {
    if(head == NULL || head->next == NULL)
        return NULL;

    struct ListNode *slow = head;
    struct ListNode *fast = head;
    struct ListNode *entry = head;

    while(fast->next && fast->next->next){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){ 
            while(slow != entry){
                slow = slow->next;
                entry = entry->next;
            }
            return entry;
        }
    }
    return NULL;
}

原因分析 #

错误代码能运行的核心原因 #

你的错误代码本质是依赖了LeetCode特定环境下的内存分配规律：

• 在LeetCode的测试环境中，链表节点是通过连续调用malloc创建的，默认的堆内存分配器（如glibc的ptmalloc）在处理连续的小内存块分配请求时，会从堆的低地址向高地址依次分配内存。
• 这意味着无环链表中，后创建的节点地址一定比前一个节点大，即cur < cur->next永远成立；而如果链表存在环，环的末尾节点会指向一个更早创建的节点（地址更小），此时cur >= cur->next的条件会触发，返回的cur->next刚好是环的入口节点。

关于malloc地址的误区 #

你提到“所有链表节点的malloc地址总是小于前一个节点”其实是搞反了——实际是后分配的节点地址比前一个大。这种规律不是malloc的强制要求，只是特定分配器在特定场景下的行为：

• malloc的地址分配策略完全由内存分配器实现决定，不同平台、不同分配器甚至不同的内存碎片情况，都会导致分配地址的变化。比如如果之前有内存被free，新的malloc可能会复用低地址的空闲块，此时新节点地址就会比旧节点小。
• 依赖指针地址比较来判断环的逻辑完全不可靠，不仅不具备通用性，在某些编程语言或架构中，指针的大小比较甚至是未定义行为。

错误代码的隐患 #

一旦脱离LeetCode的特定环境，这段代码会立刻失效：

• 若内存分配器从高地址向低地址分配，无环链表也会被误判为有环；
• 若内存存在碎片，新节点复用了之前free的低地址块，同样会触发误判；
• 无法处理环入口不是早期节点的极端情况（虽然LeetCode测试用例可能没覆盖）。

内容的提问来源于stack exchange，提问作者Rakshit Jain