Leetcode203——移除链表元素

题目描述

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

链接：Leetcode203

示例

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

示例 2**：**
**输入：**head = [ ], val = 1 输出：[ ]
示例 3：
**输入：**head = [7,7,7,7], val = 7 输出：[ ]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

核心代码模式

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 struct ListNode* removeElements(struct ListNode* head, int val)
 {
 
 }
1
2
3
4
5
6
7
8
9
10
11

思路分析与代码实现

1.前后指针原地修改法

要删掉值为val的结点，那我们就遍历链表，遇到符合条件的结点就删掉。毕竟是要删掉结点，那就设置两个指针prev和cur一前一后。cur不为NULL就一直找下去，找到要删除结点时，要注意一下是不是头结点，要是头结点的话就就是头删了，先把cur下一个结点地址给头指针head，释放掉cur位置的结点，再把head值给cur让它指向下一个结点；若不是头结点，那就先把cur下一个结点地址给prev的next指针，让prev指向cur下一个结点，释放掉cur位置的结点，再把prev下一个结点的地址给cur，让它指向下一个结点。没找到要删除的结点的话就继续找下去。

代码实现

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = head;
    struct ListNode* cur = head;

    while(cur)
    {

        if(cur->val == val)
        {
            if(cur == head)
            {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }

        }
        else
        {
            prev = cur;
            cur = cur->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
31
32
33

2.新链表尾插法

可不可以新建一个链表，定义新的头指针为newHead，然后就把值不等于val的结点放到新链表去，等于val的结点我们把它释放掉，所以我们要一个指针来遍历链表，定义cur指针。这里把值不等于val的结点放到新链表用的是尾插，那好了，尾插要是还要来个指针一个一个去找前一结点可太麻烦了，不妨定义一个尾指针tail用来指向新链表的尾部，这样尾插就方便多了。要注意有个坑，尾插到最后要记得把新链表最后一个结点的next指针给置为NULL。

代码实现

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL;
    struct ListNode* tail = NULL;

    while(cur)
    {
        if(cur->val != val)
        {

            if(tail == NULL)
            {
                newHead = cur;
                tail = cur;
            }
            else
            {

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

    return newHead;
}

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

试试带头链表

我们可以试试看用带头链表，头指的就是哨兵结点，不是用来存放有效数值的，而是用作辅助结点的。用哨兵结点在这有什么用呢？你想啊，之前不用它时是不是还要判断一下tail是不是NULL，但是用哨兵结点后tail至少是指向哨兵结点的，不会为NULL，是不是就省了点事？这里的哨兵结点我们命名为guard。

代码实现

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 = cur;
            cur = cur->next;
        }
        else
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
    }
    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