部分图文参考于：代码随想录 - 203.移除链表元素。

C++编程中记得要手动释放结点内存。

链表操作中，可以使用原链表来直接进行删除操作，也可以设置一个虚拟头结点再进行删除操作。

1.题目链接

203.移除链表元素

2.思路

以链表 1 4 2 4 来举例，移除元素4。

如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点， 清理节点内存之后如图：

在单链表中移除头结点 和 移除其他节点的操作方式不一样，需要单独写一段逻辑来处理移除头结点的情况。
针对头结点和非头结点使用不同的删除方式：
1.针对头结点等于删除值，将头结点head指向下一个值不等于val的结点。


注：别忘将原头结点从内存中删掉。

2.针对非头结点等于删除值，使用cur指向头结点，检测cur->next所指向的结点的值是否等于val。如果相等，则将cur->next指向cur->next->next，即删除结点；不相等，则将cur继续向下一个结点移动。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head && head->val == val) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
        }
        ListNode* cur = head;
        while (cur && cur->next) {
            if (cur->next->val == val) {
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
            else cur = cur->next;
        }
        return head;
    }
};

● 时间复杂度：O(n)
● 空间复杂度：O(1)

2.2.解法2：使用虚拟头结点

使用这种方式，不用再区分头结点和非头结点，原链表的所有节点就都可以按照统一的方式进行移除了。
来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。

这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。
return 头结点的时，return dummyNode->next;才是新的头结点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while (cur->next) {
            if (cur->next->val == val) {
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
            else cur = cur->next;
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

● 时间复杂度：O(n)
● 空间复杂度：O(1)