链表在第0索引处插入节点失败问题求助

问题描述 #

我编写了一个C语言链表程序，包含按索引插入节点的函数。调用该函数在索引0处插入节点时，尽管已在插入函数中更新head指针，但main函数中的head指针并未改变，遍历函数也无法打印新增元素。

代码片段 #

节点结构体 #

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

主函数 #

int main() {
    struct Node* head = NULL;
    // 初始化链表
    head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 10;
    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 20;
    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 30;
    head->next->next->next = NULL;

    printf("插入前链表：");
    traverse(head);

    // 在索引0插入节点
    insertAtIndex(head, 0, 5);

    printf("插入后链表：");
    traverse(head);
    return 0;
}

遍历打印函数 #

void traverse(struct Node* ptr) {
    while (ptr != NULL) {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

按索引插入函数 #

void insertAtIndex(struct Node* head, int index, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (index == 0) {
        newNode->next = head;
        head = newNode; // 仅修改函数内的局部指针副本
        return;
    }

    struct Node* temp = head;
    for (int i = 0; i < index - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("索引超出范围\n");
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

输出情况 #

插入后的输出与插入前完全一致，新增的节点未被打印。

问题原因 #

C语言默认采用值传递，insertAtIndex函数中的head是main函数中head指针的副本。修改这个局部指针只会改变函数内部的变量，无法影响main函数中原始指针的指向。

解决办法 #

有两种常用方案可以解决这个问题：

方案1：使用双重指针传递参数 #

修改插入函数，接收指针的指针（双重指针），直接修改原始指针的指向：

void insertAtIndex(struct Node** head, int index, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (index == 0) {
        newNode->next = *head;
        *head = newNode; // 修改原始指针的指向
        return;
    }

    struct Node* temp = *head;
    for (int i = 0; i < index - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("索引超出范围\n");
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

调用函数时传递head的地址：

insertAtIndex(&head, 0, 5);

方案2：让函数返回更新后的head指针 #

修改插入函数，使其返回更新后的链表头指针，在main函数中重新赋值：

struct Node* insertAtIndex(struct Node* head, int index, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (index == 0) {
        newNode->next = head;
        return newNode; // 返回新的头指针
    }

    struct Node* temp = head;
    for (int i = 0; i < index - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("索引超出范围\n");
        return head; // 返回原头指针
    }

    newNode->next = temp->next;
    temp->next = newNode;
    return head;
}

调用函数时重新赋值head：

head = insertAtIndex(head, 0, 5);

两种方案都能让main函数中的head指针正确指向新插入的头节点，遍历函数即可正常打印新增元素。

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