【链表OJ】一、移除链表元素

203.移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
1
2

示例 2：

输入：head = [], val = 1
输出：[]
1
2

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]
1
2

思路一：

要移除链表中值为val的结点，肯定是要遍历一遍链表的，关键是我们在遍历的过程中应该如何操作。我们考虑问题的时候，可以先考虑比较常见的情况，在考虑特殊情况。

​ 一、常见情况

​ 要移除某一结点，也就是让该结点的前一个结点指向待移除结点的后一个结点，然后将待移除的结点释放即可。所以我们需定义两个指针变量。

prev：记录待移除结点的前一个结点位置。（一开始可以置为空）

cur： 记录当前结点。

当cur指针指向的结点并非待移除的结点时，两指针依次往后移动。

当cur指针指向待移除的结点时，我们首先让prev指针指向的结点指向cur的下一个结点，然后将cur指针指向的结点释放掉，并将cur->next赋值给cur。

如此进行下去，直到链表遍历完毕。

当链表遍历完毕时，此时cur指针应该指向为空，所以遍历终止条件就是当cur为NULL的时候遍历结束。

​ 二、特殊情况

1. 当链表的第一个结点为待移除的结点时

这时我们需要将头指针指向cur结点的下一个结点，然后释放cur指向的结点，然后再将头结点赋给cur指针。

2. 当链表为空时，直接返回头指针（NULL）

代码实现

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    while(cur)
    {
        if(cur->val != val)
        {
            prev = cur;
            cur = cur->next;
        }
        else
        {
            if(cur == head)
            {
                //头删
                head = head->next;
                free(cur);
                cur = head;
            }
            else
            {
                //不是头删
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
    }
    return head;
}
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

思路二：

我们可以将不是val的结点尾插到新链表中。

这里我们需要注意的是，当最后一个结点是val时，我们需要将tail->next = NULL

代码实现

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    struct ListNode* newnode = NULL, *tail = NULL;
    while(cur)
    {
        if(cur->val != val)
        {
            if(tail == NULL)
            {
                newnode = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
    }
    if(tail)
        tail->next = NULL;

    return newnode;
}
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 ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tail = guard;
    while(cur)
    {
        if(cur->val != val)
        {
            tail->next = cur;
            tail = tail->next;

            cur = cur->next;
        }
        else
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
    }
    if(tail)
        tail->next = NULL;

    head = guard->next;
    free(guard);

    return head;
}
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