这种用于合并排序链表的递归方法是如何工作的？

Question

给定此方法：

mergeSorted(struct ListNode * a, struct ListNode * b) {

    struct ListNode * result = NULL;
    if (a == NULL) return b;
    if (b == NULL) return a;

    if (a->data <= b->data) {
        result = a;
        result->next = mergeSorted(a->next, b);
    }
    else {
        result = b;
        result->next = mergeSorted(a, b->next);
    }

    return result;
}

我知道列表是如何排序的，除了第一行，它将struct结果设置为NULL。每次递归调用该方法时，结果列表怎么会不设为NULL呢？我的第一个想法是指针被设置为NULL，而不是列表本身的实际内容，但这仍然不能让我完全理解。非常感谢您的帮助！

Answer 1

“‘result”是在函数中定义的。它不会影响此函数的其他迭代，这些迭代在其自身的局部范围内具有“result”。

每次函数返回时，它都会将“result”的本地内容附加到调用函数的“result”的末尾。

result->next = mergeSorted(..);

这个递归的return/append构建整个排序列表，并最终从它最初调用的地方返回。

Answer 2

NULL赋值被赋予一个新的struct listnode指针，该指针返回的是结果，而不是传入的值，并且这个新指针的创建和NULL赋值不会触及函数的前一次迭代的结果指针(这是一个作用域问题，新指针具有相同的名称，但不是相同的指针，因为它存在于一个全新的作用域中)。

发生的事情是你是：

• 调用此函数并将a和b的结构中的一个元素传递给它，
• 创建一个新指针来保存返回值，并将该新指针赋值为空值，
• 检查a或b是否为NULL，如果其中一个为NULL，则返回另一个(尽管这可能是函数中的一个弱点，因为如果两者都为NULL，则它将返回NULL，这可能是也可能不是，这取决于函数外部发生的事情)
• 函数然后比较当前列表节点A和B的值，
• 在此赋值之后，函数将结果结构递增到其下一个元素，并使用A和B再次调用mergeSorted (其中一个将递增到下一个值，这取决于拉取哪个值来填充结果结构)

在每一级递归中，您的结果结构只有一个值，直到递归结束并开始解开，这导致每一级递归将其结果报告给先前的迭代结果结构，直到您到达原始调用。

我唯一好奇的是这个递归实际上是如何结束的，我看不出这个东西在它处理的每个结构被消耗后会停止运行的原因(除非设置struct result = struct a以某种方式消耗了a中的所有数据并使其为空，我不再太熟悉C结构了)。