递归实现mergelist合并链表时temp如何同时关联head1和head2？

你产生这个疑问的核心原因是把递归不同调用栈里的同名局部变量当成了同一个，temp从来没有在同一时间同时持有head1和head2对应的节点。

对应实现代码如下：

Node* mergelist(Node* head1, 
                Node* head2)
{
    // 基准case
    if (!head1)
        return head2;
    if (!head2)
        return head1;
  
    Node* temp = NULL;
    if (head1->data < head2->data) 
    {
        temp = head1;
        head1->next = mergelist(head1->next, 
                                head2);
    }
    else 
    {
        temp = head2;
        head2->next = mergelist(head1, 
                                head2->next);
    }
    return temp;
}

先明确基础规则 #

• C/C++中每次函数调用都会生成独立的栈帧，每个栈帧里的入参head1、head2和局部变量temp都是独属于当前调用的，和其他层级调用的同名变量没有共享关系，修改某一层的变量不会影响其他层。
• 单个指针变量同一时间只能存储一个内存地址，从语法层面就不可能同时持有两个独立节点的地址。

结合最小执行流程拆解 #

拿最简单的两个有序链表演示：head1 = 1->3，head2 = 2->4，递归执行和返回的全过程如下：

1. 最外层（第一层）调用：当前head1指向值为1的节点，head2指向值为2的节点，1更小，因此这一层的temp存储1节点的地址。接下来递归调用mergelist(3节点, 2节点)，等待返回结果后挂到1节点的next指针上。
2. 第二层调用：当前入参head1指向3节点，head2指向2节点，2更小，因此这一层的temp存储2节点的地址。接下来递归调用mergelist(3节点,4节点)，等待返回结果后挂到2节点的next指针上。
3. 第三层调用：当前入参head1指向3节点，head2指向4节点，3更小，因此这一层的temp存储3节点的地址。接下来递归调用mergelist(nullptr,4节点)。
4. 第四层调用：触发基准case，head1为空，直接返回4节点的地址。

之后逐层弹栈返回：

• 第三层拿到第四层返回的4节点地址，挂到3节点的next上，返回本层temp存储的3节点地址。
• 第二层拿到第三层返回的3节点地址，挂到2节点的next上，返回本层temp存储的2节点地址。
• 第一层拿到第二层返回的2节点地址，挂到1节点的next上，返回本层temp存储的1节点地址，也就是最终合并完的链表头。

temp的实际作用 #

每一层的temp只做一件事：暂存当前层对比两个链表头后选出的、值更小的那个节点地址。等递归调用把剩余两段链表合并完成、挂到这个选中节点的next上之后，直接把这个选中节点返回给上一层即可。层层返回的过程中，各层选中的节点会自动串成完整的有序链表，根本不需要单个temp同时持有两个节点。

内容的提问来源于stack exchange，提问作者ratim shariar