扁平化链表问题中merge函数传引用引发编译错误的原因咨询

问题场景 #

在实现扁平化链表的过程中，调用merge函数时触发编译错误，错误信息如下：

Compilation Failed
In file included from runner.c++:21:0:
solution.h: In function 'Node* flattenLinkedList(Node*)':
solution.h:61:38: error: invalid initialization of non-const reference of type 'Node*&' from an rvalue of type 'Node*'
  return merge(head, flattenLinkedList(head->next));
                                      ^
solution.h:14:7: note:   initializing argument 2 of 'Node* merge(Node*&, Node*&)'
 Node* merge(Node* &a, Node* &b){
       ^

用户的代码实现：

/*
 * Definition for linked list.
 * class Node {
 *  public:
 *      int data;
 *      Node *next;
 *      Node *child;
 *      Node() : data(0), next(nullptr), child(nullptr){};
 *      Node(int x) : data(x), next(nullptr), child(nullptr) {}
 *      Node(int x, Node *next, Node *child) : data(x), next(next), child(child) {}
 * };
 */

Node* merge(Node* &a, Node* &b){
    
    Node* temp = new Node(0);
    Node* ans = temp;
    
    while(a!=NULL && b!=NULL){
        
        if(a->data < b->data){
            ans->child = a;
            ans = a;
            ans->next = NULL;
            a = a->child;       
        }
        else{
            ans->child = b;
            ans = b;
            ans->next = NULL;
            b = b->child;
        }
    }

    while(a!=NULL){
        ans->child = a;
        ans = a;
        ans->next = NULL;
        a = a->child;
    }
    
    while(b!=NULL){
        ans->child = b;
        ans = b;
        ans->next = NULL;
        b = b->child;
    }
    
    temp = temp->child;
    ans->child = NULL;
    return temp;
}

Node* flattenLinkedList(Node* head) 
{
    // Write your code here
    if (head == NULL || head->next==NULL) {
        return head;
    }

    return merge(head, flattenLinkedList(head->next));
}

错误原因 #

1. C++引用绑定规则限制：非const左值引用（Node* &）只能绑定到可修改的左值，不能绑定到右值。而flattenLinkedList(head->next)的返回值是临时的Node*对象，属于右值，无法满足非const引用的绑定要求，因此触发编译错误。
2. 不必要的引用传递：你的merge函数中对a和b的修改（如a = a->child）只是为了遍历链表，不需要影响函数外部的原指针变量，完全没必要使用引用传递指针。

修复方案 #

将merge函数的参数改为值传递（去掉引用符号&），因为指针本身是内存地址，值传递的开销可以忽略，且不会影响函数外部的变量。修改后的函数声明如下：

Node* merge(Node* a, Node* b){
    // 函数体逻辑保持不变，内部修改的是a和b的副本，不影响外部
}

修改后，调用merge(head, flattenLinkedList(head->next))时，右值可以正常传递给值传递参数，编译错误即可解决。

内容的提问来源于stack exchange，提问作者Jahnvi Agarwal