C++链表插入操作中为何push/append用二级指针而insertAfter用一级指针

问题1：为什么push、append用二级指针，insertAfter只用一级指针 #

核心原因是两种操作需要修改的目标对象不同，结合C/C++默认值传递的特性就产生了参数类型的差异：

• C/C++默认使用值传递，函数内修改形参默认不会影响外部实参的实际值
• push头插、append尾插两个操作，存在需要修改外部头指针本身的值的场景：
  • 头插操作无论链表是否为空，都要把外部的头指针指向新插入的节点
  • 尾插操作如果链表原本为空，也需要把外部的头指针从NULL修改为新节点的地址
  • 要修改Node*类型的头指针变量的值，就需要传入该变量的地址，也就是Node**二级指针，通过*head_ref就能直接修改外部头指针本身的取值
• insertAfter操作不需要修改传入的prev_node指针本身的值，只需要修改prev_node指向的节点对象里的next成员：
  • 哪怕是值传递传入prev_node，形参只是实参的副本，二者存储的地址完全相同，指向同一个节点对象
  • 通过prev_node->next修改的是节点对象的成员，天然会作用到原对象上，不需要修改指针本身的取值，所以一级指针足够

问题2：可以用一级指针替代二级指针实现相同功能 #

完全可以，常见的有两种实现方案：

方案1：函数返回新的头指针 #

把插入函数的返回值设为Node*，操作完成后返回最新的头指针，外部调用时主动用原头指针接收返回值即可，示例如下：

// 头插改造示例
Node* push(Node* head, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = head;
    return new_node;
}

// 尾插改造示例
Node* append(Node* head, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = NULL;
    if (head == NULL) {
        return new_node;
    }
    Node* last = head;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
    return head;
}

// 调用方式
int main() {
    Node* head = NULL;
    head = append(head, 6);
    head = push(head, 7);
    // 后续操作逻辑不变
}

注意：该方案必须保证每次调用都将返回值赋值给原头指针，否则会出现修改不生效、内存泄漏的问题。

方案2：使用C指针引用（仅C支持） #

C++支持引用传递，可以直接传入指针的引用，形参是外部实参的别名，修改形参就等价于修改外部的头指针，不需要二级指针，示例如下：

// 头插改造示例
void push(Node*& head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = head_ref;
    head_ref = new_node;
}

// 调用方式，不需要对头指针取地址
int main() {
    Node* head = NULL;
    push(head, 7);
    append(head, 6);
    // 后续操作逻辑不变
}

注意：该方案是C++特有的语法，C语言不支持，原版代码用二级指针的写法是为了兼容C语言，跨语言通用性更强。

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