《Hello算法》5、链表的节点删除

lugl4313820

《Hello算法》5、链表的节点删除 [复制链接]

 

《Hello算法》5、创建链表

《Hello算法》5、链表插入

在前面我学习了链表的创建与插入。下面继续学习链表节点的删除。

链表的删除，有几种情况:

1、本身链表为空，那就直接返回。

2、链表只有一个节点，那就直接把链表的内存释放，然后把链表指向NULL。

3、如果要删除的链表是首节点，那么把链表指下一个节点。

4、如果是尾节点，那么就把减一个节点的指针指向空，然后释放尾节点。

5、如果是中间的节点，那就把后一节点的next指向下一个节点的head。

首先创建三个节点，来测试：

复制

登录后复制

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

//写一个创建节点的函数
struct node {
    int data;
    struct node *next;
};
struct node *create_node(int data) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    p->data = data;
    p->next = NULL;
    return p;
}
//写一个插入节点的函数
struct node *insert_node(struct node *head, int data) {
    struct node *p = create_node(data);
    p->next = head;
    return p;
}
//写一个遍历节点的函数
void traverse_node(struct node *head) {
    struct node *p = head;
    while (p != NULL) {
        printf("%d \r\n", p->data);
        p = p->next;
    }
    printf("打印结束\n");
}

//写一个释放所有节点的函数
void free_node(struct node *head) {
    struct node *p = head;
    while (p != NULL) {
        struct node *tmp = p;
        p = p->next;
       
       free(tmp);
    }
    printf("释放链表结束\n");
}

int main() {
    //创建一个链表
    struct node *head = create_node(1);
    head = insert_node(head, 2);
    //插入1个节点
    head = insert_node(head, 3);
    //打印链表
    traverse_node(head);
    free_node(head);
    return 0;
}

编译后运行：

复制

登录后复制

liujianhua@liujianhuadeMac-mini HelloC % gcc node_test.c
liujianhua@liujianhuadeMac-mini HelloC % ./a.out        
3 
2 
1 
打印结束
释放链表结束
liujianhua@liujianhuadeMac-mini HelloC % 

在书中给他的示例为：

复制

登录后复制

/* 删除链表的节点 n0 之后的首个节点 */
// 注意：stdio.h 占用了 remove 关键词
void removeItem(ListNode *n0) {
    if (!n0->next)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 释放内存
    free(P);
}

然后我使用AI生成了删除节点的函数：

复制

登录后复制

/**
 * 删除链表中的一个节点
 * 
 * @param head 链表的头节点指针
 * @param data 要删除的节点的数据值
 * [url=home.php?mod=space&uid=784970]@return[/url] 返回删除节点后的链表头节点指针
 *
 * 此函数遍历链表，寻找数据值匹配的节点，并将其从链表中删除
 * 如果找到了匹配的节点，将其释放并返回删除节点后的链表头节点指针
 * 如果没有找到匹配的节点，则返回原始的链表头节点指针
 */
struct node *delete_node(struct node *head, int data) {
    // 初始化指针p，用于遍历链表
    struct node *p = head;
    
    // 遍历链表，直到指针p为NULL
    while (p != NULL) {
        // 检查当前节点的数据值是否与要删除的值匹配
        if (p->data == data) {
            // 如果匹配，保存当前节点的指针到tmp
            struct node *tmp = p;
            // 指针p指向下一个节点
            p = p->next;
            // 释放匹配节点的内存
            free(tmp);
            // 返回链表的头节点指针
            return head;
        }
        // 如果当前节点数据值不匹配，则移动到下一个节点
        p = p->next;
    }   
    // 如果没有找到匹配的节点，返回原始的头节点指针
    return head;
}

为了测试效果，我编写主程序如下：

复制

登录后复制

int main() {
    //创建一个链表
    struct node *head = create_node(1);
    head = insert_node(head, 2);
    //插入1个节点
    head = insert_node(head, 3);
    //打印链表
    traverse_node(head);
    head = delete_node(head, 2);
    traverse_node(head);
    free_node(head);
    return 0;
}

测试效果：

复制

登录后复制

liujianhua@liujianhuadeMac-mini HelloC % gcc node_test.c
liujianhua@liujianhuadeMac-mini HelloC % ./a.out        
3 
2 
1 
打印结束
数据为：2 删除成功
3 
684081200 

但是好象出错了：

重写：

复制

登录后复制

// 写一个删除节点的函数
struct node *delete_node(struct node *head, int data) {
    // 如果要删除的是头节点
    if (head != NULL && head->data == data) {
        struct node *tmp = head;
        head = head->next;
        free(tmp);
        return head;
    }

    // 遍历链表寻找要删除的节点
    struct node *current = head;
    while (current != NULL && current->next != NULL) {
        if (current->next->data == data) {
            struct node *tmp = current->next;
            current->next = current->next->next;
            free(tmp);
            return head;
        }
        current = current->next;
    }

    // 如果没有找到要删除的节点，返回原始头节点
    return head;
}

测试：

复制

登录后复制

liujianhua@liujianhuadeMac-mini HelloC % ./a.out        
3 
2 
1 
打印结束
3 
2 
打印结束
释放链表结束

【总结】

删除链表的节点，需要考虑许多特殊的情况。但是相比数组，删除链表的速度要快一些。

还有就是在插入链表时，需要考虑是尾插还是前插。

查看本帖全部内容，请登录或者注册

Jacktang

要删除的链表是首节点，那么把链表指下一个节点，有这种情况