从单链表中删除节点

Question

我有一个简单的函数，可以从单个链表中搜索具有给定键的节点并将其删除。当拥有给定键的节点无处不在时，该函数起作用，除非该节点是列表的头部。为什么会这样？

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


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

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

/* Given a reference (pointer to pointer) to the head of a list 
   and a key, deletes the first occurrence of key in linked list */
void deleteNode(struct Node* head, int key){
    if(head->data==key){
        head = head->next;
    }
    else {
        while(head->next->data!=key){
            head = head->next;
        }
        head->next = head->next->next;
    }
}

int main(){

    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    second->data = 2;
    third->data = 3;
    first->next = second;
    second->next = third;
    third->next = NULL;

    printlist(first); // prints 123

    deleteNode(first, 2);  
    printlist(first); // prints 13

    deleteNode(first, 1);
    printlist(first); // still prints 13
}

Answer 1

当您调用此函数时：void deleteNode(struct Node* head, int key) 的第一个参数是指向 Node 结构的指针（就像您在 main 中所做的那样），那么该函数是什么作为第一个参数接收的是您提供的指针的副本!

您可能知道一个函数：void Increment(int n) 可以对它传递的 n 做任何它喜欢的事情，而无需更改调用模块中的变量。所以，如果你想让函数真正改变调用块中的值，你给它一个指针：

void Increment(int* n) {
    ++(*n);
}

同样，如果你想让一个函数改变一个指针，那么你必须向它传递一个指向那个指针的指针。试试这个：

void deleteNode(struct Node** head, int key){
    Node* temp = *head;
    if(temp->data==key){
        *head = temp->next; // Only need to change *head if its the first one ...
    }
    else {
        while(temp->next->data!=key){
            temp = temp->next;
        }
        temp->next = temp->next->next; // ... else we have already changed the actual "links"
    }
}

并且，在 main 中，使用：

deleteNode(&first, 2);

和：

deleteNode(&first, 1);

让我们知道发生了什么。

注意：顺便说一句，这不是 "best possible code" - 删除 link 而没有实际删除指向的对象，您将造成内存泄漏。

注2：另外，如果key没有找到，你的代码会"fall off"结束列表，当它找到NULL时next指针！

Answer 2

函数处理原始头的副本。因此副本的更改不会影响原始节点。您应该通过指针通过引用传递头节点，或者从更改的头节点的函数中传递 return。您还必须在函数的开头检查头节点是否等于 NULL。否则该函数可以调用未定义的行为。

例如

void deleteNode( struct Node **head, int key )
{
    while( *head != NULL && ( *head )->data != key ) head = &( *head )->next;

    if ( *head != NULL ) *head = ( *head )->next;
}

然后这样称呼它

deleteNode( &first, 1 );

这是一个演示程序

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

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

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

/* Given a reference (pointer to pointer) to the head of a list 
   and a key, deletes the first occurrence of key in linked list */
void deleteNode( struct Node **head, int key )
{
    while( *head != NULL && ( *head )->data != key ) head = &( *head )->next;

    if ( *head != NULL ) *head = ( *head )->next;
}

int main(){

    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    second->data = 2;
    third->data = 3;
    first->next = second;
    second->next = third;
    third->next = NULL;

    printlist(first); // prints 123

    deleteNode(&first, 2);  
    printlist(first); // prints 13

    deleteNode(&first, 1);
    printlist(first); // still prints 13
}

它的输出是

123
13
3

或

struct Node * deleteNode( struct Node *head, int key )
{
    if ( head != NULL )
    {
        if ( head->data == key )
        {
            head = head->next;
        }
        else 
        {
            struct Node *current = head;
            while( current->next != NULL && current->next->data != key )
            {
                current = current->next;
            }
            if ( current->next != NULL ) current->next = current->next->next;
        }
    }

    return head;
}

并称其为

first = deleteNode( first, 1 );

这是另一个演示程序

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

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

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

/* Given a reference (pointer to pointer) to the head of a list 
   and a key, deletes the first occurrence of key in linked list */
    struct Node * deleteNode( struct Node *head, int key )
    {
        if ( head != NULL )
        {
            if ( head->data == key )
            {
                head = head->next;
            }
            else 
            {
                struct Node *current = head;
                while( current->next != NULL && current->next->data != key )
                {
                    current = current->next;
                }
                if ( current->next != NULL ) current->next = current->next->next;
            }
        }

        return head;
    }

int main(){

    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    second->data = 2;
    third->data = 3;
    first->next = second;
    second->next = third;
    third->next = NULL;

    printlist(first); // prints 123

    first = deleteNode(first, 2);  
    printlist(first); // prints 13

    first = deleteNode(first, 1);
    printlist(first); // still prints 13
}

它的输出同样是

123
13
3

一般情况下，列表的节点是动态分配的。所以删除节点的函数也应该释放被删除的节点或者return它从函数中释放。

从单链表中删除节点

deleting node from a singly linked list

c

reference

linked-list

singly-linked-list