Leetcode 链表 II 问题 142.错误的解决方案，但它为什么有效？-解网

问：

这是我用 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;
    }

换句话说，它总是可以表示为为什么所有节点的地址总是比以前少？

c malloc 单链接列表

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

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

假设调用了错误的函数并调用了正确的实现，然后尝试运行上述测试用例：detectCycleWrongdetectCycleCorrect

    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。

Leetcode 链表 II 问题 142.错误的解决方案，但它为什么有效？

Leetcode Linked List II question No. 142.Wrong Solution but why does it work?

评论

评论