1、题目描述

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

示例 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

2、分析

没啥说的。

另外，在实现的时候无论用一个指针还是两个指针都是可以的；节点值是否等于val的if……else逻辑区分清楚就好。

2.1、一个指针的实现

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode dummy(0, head);ListNode *cur = &dummy;while(cur->next){//如果cur.next就是目标节点。那么,cur保持不变、将cur->next指向下一个节点。if(cur->next->val == val){cur->next = cur->next->next;//如果cur.next不是目标节点。那么,cur后移一步即可。}else{cur = cur->next;}}return dummy.next;}
};

2.2、使用两个指针

一个指针指向pre、一个指针指向cur。

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode dummy(0, head);ListNode *pre = &dummy;ListNode *cur = pre->next;while(cur){//如果是要删除的节点。则:cur后移、pre不变、pre->next要更新if(cur->val == val){cur = cur->next;pre->next = cur;//如果不是要删除的节点。则: cur后移、pre也后移}else{cur = cur->next;pre = pre->next;}}return dummy.next;}
};

3、实现代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>using namespace std;struct ListNode{int val;ListNode * next;ListNode(): val(0), next(nullptr){}ListNode(int x): val(x), next(nullptr) {}ListNode(int x, ListNode* n): val(x), next(n) {}
};class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode dummy(0, head);ListNode *cur = &dummy;while(cur->next){//如果cur.next就是目标节点。那么,cur保持不变、将cur->next指向下一个节点。if(cur->next->val == val){cur->next = cur->next->next;//如果cur.next不是目标节点。那么,cur后移一步即可。}else{cur = cur->next;}}return dummy.next;}
};void printList(ListNode* head){while(head){cout << head->val << ",";head = head->next;}cout << endl;
}int main()
{Solution s1;ListNode n5(7);ListNode n4(7, &n5);ListNode n3(7, &n4);ListNode n2(7, &n3);ListNode n1(7, &n2);printList(&n1);ListNode* new_head = s1.removeElements(&n1, 7);printList(new_head);
}