c语言 - 在链表的第n个位置插入一个节点;这段代码出了什么问题？

Question

我有这个函数在链表的特定位置插入新数据，但它不工作:

Node* InsertNth(Node *head, int data, int position) {
    struct Node *h = head; 
    struct Node *p = (struct Node *)malloc(sizeof(struct Node));
    for (i=0; i<position; i++)   
        { h = h->next; }
    p->next = h;  // what's wrong in this line 
    h = p;        // what's wrong in this line
}

如果我在for循环中将i=0更改为i=1，并将"what's wrong"注释行中的h更改为h->next，结果很好，我已经看到了这个问题的许多解决方案。每个人都写i=1和h->next，但为什么不写i=0和h呢?

Answer 1

在链表中间插入节点时，需要更新前一个节点的next字段，该节点位于指向新节点的位置之前。

当在链表的前面插入一个节点时，您需要更新列表的head指针以指向新节点，该节点现在指向next字段中的旧头。

您没有在代码中做这些事情，因此p实际上根本没有被添加到列表中。你只是在泄漏它的内存。

您也没有验证position是否在列表的范围内。如果position太大，您的代码将最终访问NULL指针并崩溃。

说了这些，试着这样做:

Node* InsertNth(Node **head, int data, int position) {
    if ((!head) || (position < 0)) return NULL;
    struct Node *h = *head;
    struct Node *prev = NULL;
    for(int i = 0; i < position; ++i) {
        if (!h) return NULL;   
        prev = h;
        h = h->next;
    }
    struct Node *p = (struct Node *) malloc(sizeof(struct Node));
    if (!p) return NULL;
    p->data = data;
    p->next = h;
    if (prev) prev->next = p;
    if (*head == h) *head = p;
    return p;
}

Node *list = NULL;
// add nodes as needed...
...
Node *n = InsertNth(&list, data, position);
if (n) {
    // success 
} else {
    // error
}