203. 移除链表元素

题目链接：203.移除链表元素
题目内容：

理解题意：就是单纯的删除链表中所有值等于给定的val的节点。上一篇博客中介绍了链表的基础操作，在删除链表中节点时，需要注意的是头节点：

• 如果没有虚拟头节点，那么对头节点的删除需要做不同的处理，head = head->next；
• 如果有虚拟头节点，那么所有的节点操作都是一致的，将待删除节点的前驱节点和后驱节点连接起来，并释放待删除节点对应的地址空间。

另外，由于链表的定义就是递归的，因此可以考虑使用递归，从最后一个节点开始，判断是否满足待删除条件。

解法①：头节点单独判断

在没有虚拟头节点的情况下，头节点需要单独判断。如果头节点的值就等于val，那么新的头节点head = head->next。然后呢？此时的新head对应节点的值是否等于val呢，如果等于val，那么新的头节点也要删除，删除以后head再次赋值head = head->next。 那么新的head又和给定val相等吗？ ——不难发现，判断头节点是否等于val这里应该是循环的，循环直到head->val != va或者head == nullptr才行。
代码如下（C++）：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//单独判断头节点 【用循环】while(head && head->val == val){head = head->next;}ListNode *preNode = NULL, *currNode = head; //preNode是前驱节点，currNode是当前节点while(currNode){//删除节点if(currNode->val == val){preNode->next = currNode->next;delete currNode;currNode = preNode->next;}//直接后移else{preNode = currNode;currNode = currNode->next;}}return head;}
};

如果不一开始就判断头节点，而是在查找值等于val的节点，并删除的过程中，对头节点单独处理的话，怎么知道当前节点是头节点呢？ ——删除节点的时候，需要有当前节点currNode的指针，也需要其前驱节点preNode的指针【删除节点的时候，需要将其前驱节点的next指向后驱节点。单向链表通过当前节点可以找到后驱节点，但是不用一个变量存前驱节点的话，是不能通过当前节点直接定位到前驱节点的。】如果当前节点是头节点的话，preNode是NULL，代码如下（C++）：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* currNode = head;ListNode* preNode = NULL;while(currNode != nullptr){//当前节点和目标val相等，删除if(currNode->val == val){//删除的是头节点if(preNode == NULL){                  head = currNode->next; //新headdelete currNode;currNode = head;                }//删除其他节点else{                     preNode->next = currNode->next;delete currNode;currNode = preNode->next;                   } }//当前节点和目标val不相等，preNode和currNode直接向后移动else{preNode = currNode;currNode = currNode->next;}}return head;}
};

解法②：虚拟头节点

添加一个虚拟头节点，那么原链表中所有节点操作都一样，不需要对头节点单独判断，代码如下（C++）：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode *dummyhead = new ListNode(0);//构造一个虚拟头节点dummyhead->next = head; //将head赋值给其next，建立dummyhead和head之间的连接ListNode *currNode = head, *preNode = dummyhead; //当前节点、前驱节点while(currNode){//删除节点if(currNode->val == val){preNode->next = currNode->next;delete currNode;currNode = preNode->next;}else{preNode = currNode;currNode =currNode->next;}}head = dummyhead->next;delete dummyhead; return head;}
};

解法③：递归

链表的定义就是递归的，因此可以考虑用递归的方法求解。
思路：①寻找递归终止条件，是head=null；②对于当前节点head，递归调用删除节点的函数，去删除当前节点之后的链表里面满足题意的节点【即removeElements(head->next, val)】，并返回剩下链表删除节点后的头节点；并将removeElements()返回的结果赋值给head->next；③对于当前节点，判断是否满足题意，如果等于val就删除，那么包括当前节点head在内的这一段链表的头节点就是head->next，返回head->next；如果不删除，就直接返回head。

代码如下（C++）：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//递归终止条件是head=null，即一直递归调用到最后一个节点的nextif(head == nullptr)return head;//当前节点的next指向后半截链表删除节点后返回的头节点head->next = removeElements( head->next ,val);//判断当前节点是否需要删除if(head->val == val)return head->next;elsereturn head;}
};

递归求解，不仅要遍历链表各个节点并判断，并且涉及到函数的递归调用，时间和空间开销都比之前解法要大。