Stone's Note
0%

利用二级指针删除单向链表

发表于 更新于

Reference & Thanks

这篇文章给我很大的启示，自己也属于不会使用指针的一类人，自己手动敲代码，实现一下。

场景：

有一个链表，链表里的val是int型，删除指定val对应的节点，各个节点val不重复

链表节点：

1
2
3
4
struct node {
    int val;
    struct node *next;
};

“常规方式”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct node* remove_tra(struct node* begin, int del)
{
    struct node *ptr = begin, *tmp = NULL;

    // 若删除节点为第一个节点，需特殊处理
    if (ptr->val == del)
    {   
        begin = begin->next;
        free(ptr);
    }   
    else
    {   
        while (ptr->next != NULL)   
        {   
            if (ptr->next->val == del)
            {   
                tmp = ptr->next;
                ptr->next = ptr->next->next;

                free(tmp);
                break;
            }   

            ptr = ptr->next;
        }   
    }   

    // 若删除的是第一个节点，则头指针被修改，则需函数返回时重新赋值
    return begin;
}

“二级指针方式”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void remove_two_level(struct node** new, int del)
{
    struct node *tmp = NULL;

    while ((*new) != NULL)
    {   
        if ((*new)->val == del)
        {   
            tmp = *new;
            *new = (*new)->next;

            free(tmp);
            break;
        }   

        new = &(*new)->next;
    }   

    // 不需特殊处理，不需返回值
}

总结

  • 二级指针方式代码量更少
  • 不需要“删除当前节点，需要记住当前节点之前的节点”这种很繁琐的方式
  • 当可能修改第一个节点时，不需要额外逻辑，也不需要返回新头指针

“全部代码”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include <stdlib.h>
#include <error.h>


#define NUM 10

struct node {
    int val;
    struct node *next;
};


void myOutput(struct node* ptr)
{
    while (ptr != NULL)
    {   
        printf("%d\n", ptr->val);
        ptr = ptr->next;
    }   
}

// 常规方式
struct node* remove_tra(struct node* begin, int del)
{
    struct node *ptr = begin, *tmp = NULL;

    if (ptr->val == del)
    {   
        begin = begin->next;
        free(ptr);
    }   
    else
    {   
        while (ptr->next != NULL)   
        {   
            if (ptr->next->val == del)
            {   
                tmp = ptr->next;
                ptr->next = ptr->next->next;

                free(tmp);
                break;
            }   

            ptr = ptr->next;
        }   
    }   

    return begin;
}

// 二级指针
void remove_two_level(struct node** new, int del)
{
    struct node *tmp = NULL;

    while ((*new) != NULL)
    {   
        if ((*new)->val == del)
        {   
            tmp = *new;
            *new = (*new)->next;

            free(tmp);
            break;
        }   

        new = &(*new)->next;
    }   
}


int main(int argc, char** argv)
{
    int i = 0, del = 0;
    struct node *ptr = NULL, *begin = NULL, *tmp = NULL;

    for (; i < NUM; ++i)
    {   
        tmp = (struct node*)malloc(sizeof(struct node));

        if (NULL == tmp)
            perror("malloc");
        tmp->val = i;
        tmp->next = NULL;

        if (NULL == begin)
            begin = tmp;
        else
            ptr->next = tmp;

        ptr = tmp;
    }


    printf("input the delete element: 0 - %d\n", NUM - 1);
    scanf("%d", &del);
    if (del < 0 || del >= NUM)
        perror("input invalid");
    
	printf("delete element: %d\n", del);

    // begin = remove_tra(begin, del);
    remove_two_level(&begin, del);

    myOutput(begin);

    return 0;
}