给你一个链表的头节点 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 <= 500 <= val <= 50
初始代码
/**
* 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) {
}
};
解题思路
递归
又是链表相关的递归题。意味着我们要用栈的思维,从链表的最后一个节点往前看。
最后一个节点的val可能相等,所以我们递归应该递归到链表最后的空节点NULL。递归到该节点时,将NULL返回给链表尾节点的next。这样如果链表中就一个节点,删除该节点后链表也能置空。
和用迭代法删节点一样,我们要删除B节点前,得有它的上一个节点的next。这样我们才能把A的next指针从指向B节点改为指向C节点。那么递归的时候也是一样,代码如下
head->next=removeElements(head->next,val);
递归到最后时需要判断是否等于给定的val,相等就将B->next作为返回值,返回给A->next,从而实现A的next指向B->next即C节点的操作。
完整代码
/**
* 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) {
if(head==NULL)
return NULL;
head->next=removeElements(head->next,val);
if(head->val==val)
return head->next;
else
return head;
}
};