Leetcode链表二第142题，解法错误，但为什么能成功？

Question

这是我在leetcode中写的代码，我知道它的实现是错误的，但为什么会这样呢？

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 *fastp = head , *slowp = 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;
    }

在其他方面，它总是可以表达为为什么所有节点总是分配比以前更少的地址？

Answer 1

错误代码假设不同节点的内存地址随着列表的遍历而增加。依赖列表中已分配节点的地址当然是错误的。如果所有测试用例都通过，这意味着测试用例分配内存的方式允许该逻辑给出正确的答案。例如，如果节点的分配顺序与添加到列表中的顺序相同，则连续节点的内存地址更有可能增加，而不是情况并非如此。

这是一个可能会使用错误代码产生错误结果的测试用例：它创建一个链表 1→2→3→4→5→2（其中只有一个值为 2 的节点）。但节点的分配以不同的顺序发生，节点 2 分配为last。

假设错误的函数被称为

detectCycleWrong

，正确的实现被称为

detectCycleCorrect

，然后尝试运行上述测试用例：

    struct ListNode *one = createNode(1);
    struct ListNode *three = createNode(3);
    struct ListNode *four = createNode(4);
    struct ListNode *five = createNode(5);
    // Allocated last: the node that will close the cycle
    struct ListNode *two = createNode(2);
 
    one->next = two;
    two->next = three;
    three->next = four;
    four->next = five;
    five->next = two;  // Back link
    
    struct ListNode *resultCorrect = detectCycleCorrect(one);
    printf("cycle at: %d\n", resultCorrect ? resultCorrect->val : -1);  // 2
    
    struct ListNode *resultWrong = detectCycleWrong(one);
    printf("cycle at: %d\n", resultWrong ? resultWrong->val : -1);  // 3?

正确的实现将输出 2，但错误的实现很可能（但不保证）输出 3。