LeetCode每日一练 —— 203. 移除链表元素

前言

Wassup guys！我是Edison

今天是 LeetCode 上的 leetcode 203. 移除链表元素

Let’s get it！

---

---

1. 题目分析

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

示例 1：

示例 2：

示例 3：

2. 题目图解

这道题很简单，还是采用 双指针 法，但是要考虑几种情况

（1）常规情况
 
（2）链表中有连续的 val
 
（3）头节点就是 val

常规情况

定义一个 prev 指针指向 NULL；再定义一个 cur 指针指向头节点

第 1 步：cur 指向的元素不等于 6，那么 prev 和 cur 依次向后挪动（如图所示）

第 2 步：cur 指向的元素不等于 6，那么 prev 和 cur 依次向后挪动（如图所示）

第 3 步：此时 cur 指向的元素等于 6，那么元素 6 置为 NULL，然后让 prev 的 next 指向元素 3，cur 的 next 也指向元素 3 （如图所示）

第 4 步：cur 指向的元素不等于 6，那么 prev 和 cur 依次向后挪动（如图所示）

第 5 步：cur 指向的元素不等于 6，那么 prev 和 cur 依次向后挪动（如图所示）

第 6 步：此时 cur 指向的元素等于 6，那么元素 6 置为 NULL，然后让 prev 的 next 指向 cur 的 next（如图所示）

第 7 步：当 cur 指向的元素为 空 时，循环就终止了（如图所示）

动图演示

连续 val 情况

还是定义一个 prev 指针指向 NULL；再定义一个 cur 指针指向头节点（如图所示）。

第 1 步：cur 指向的元素不等于 6，那么 prev 和 cur 依次向后挪动（如图所示）

第 2 步：cur 指向的元素不等于 6，那么 prev 和 cur 依次向后挪动（如图所示）

第 3 步：此时 cur 指向的元素等于 6，那么删除该元素，然后让 prev 的 next 指向 cur 的 next，cur 指向下一个元素（如图所示）

第 4 步：此时 cur 指向的元素还是等于 6，那么删除该元素，然后让 prev 的 next 指向 cur 的 next，cur 指向下一个元素（如图所示）

第 5 步：此时 cur 指向的元素还是等于 6，那么删除该元素，然后让 prev 的 next 指向 cur 的 next，cur 指向下一个元素（如图所示）

第 6 步：此时 cur 指向的元素不是 6，那么 prev 和 cur 依次向后挪动（如图所示）

第 7 步：此时 cur 指向的元素等于 6，那么删除该元素然后让 prev 的 next 指向 cur 的 next，cur 指向 空，终止循环（如图所示）

可以看到，如果链表中有连续的 val，那么做法也是和常规情况一样的。

头节点就为 val

还是定义一个 prev 指针指向 NULL；再定义一个 cur 指针指向头节点（如图所示）。

此时可以发现一个问题，如果是按照常规情况来算的是，cur 指向的元素等于 6，那么删除该元素，然后让 prev 的 next 指向 cur 的 next，cur 指向下一个元素。

但是此时 prev 指向的元素为 空， cur 的 next 怎么能够赋值给 空 呢？显然是不行的，得另想办法！

其实很简单，我们再定义一个 curHead 指针指向头节点（如图所示）。

这里直接用一个动图来演示整个过程

3. 代码实现

接口代码

struct ListNode* removeElements(struct ListNode* head, int val){
    
    struct ListNode* prev, *cur;
    prev = NULL;
    cur = head;
    // 循环的结束条件就是cur等于空
    while (cur) {
    
        // cur不等于val
        if (cur->val != val) {
    
            prev = cur; //直接把cur的地址赋给prev，相当于把prev移动到cur的位置上
            cur = cur->next; // cur也向后移动一个位置
        }
        else {
     // 当cur等于val
            struct ListNode* curHead = cur->next; 
            // 为什么 curHead 的内容为 cur->next, 而不是cur呢？
            // 假设头节点就等于val,那么删除val以后, 就相当于头删
            // 头删之后，如果curHead是内容是cur的地址的话，那么久找不到后面的链表了
            // 所以curHead存的应该是cur->next, 也就是第二个节点的地址
            if (prev == NULL) {
     // 头节点为val为val的情况
                free(cur); // 释放掉cur
                head = curHead; // 更新头节点
                cur = curHead; // 然后把新的头节点的地址赋给cur
            }
            else {
     // 头节点不为val为val的情况
                free(cur); // 释放val元素
                prev->next = curHead; // 因为curHead存的是cur的next,也就是cur的下一个节点的地址,所以直接赋给prev的next
                cur = curHead; // 然后让cur指向下一个节点的地址
            }
        }
    }
    return head;
}

提交结果