Leetcode203

链表移除元素

Leetcode203

题目描述

给你一个链表的头节点 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
输出：[]

思路

普通做法

普通做法就是将删除节点为头节点和非头节点分开处理的方法。

• 删除节点为头节点：头节点改为下一个节点，循环删除，直至头节点不为删除节点
• 删除节点为非头节点：遍历节点即可，找到删除的节点，将其上一个节点的尾部指向该删除节点的下一个节点，因为是单链表，需要记录上一节点，也可以用prev->next为当前节点。

代码如下：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

虚拟头节点法

创建一个新的不会被删除的头节点，其next指向head，这样一来所有节点都为非空节点，直接按非空节点删除即可。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* virtulNode = new ListNode(-1,head); //虚拟节点
        ListNode* prev = virtulNode; 
        while(prev->next!=NULL){
            if(prev->next->val == val){
                ListNode* temp = prev->next;
                prev->next = prev->next->next;
                delete temp;
            }else{
                prev = prev->next;
            }
        }
        return virtulNode->next;
    }
};

递归法

递归删除节点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == NULL) return head;
        head->next = removeElements(head->next,val);
        if(head->val == val){
            ListNode* next = head->next;
            delete head;
            return next;
        }else{
            return head;
        }
    }
};

简单来说，就是，一直递归调用到最后一个元素，从最后一个元素开始删除，如果传进来的节点是一个要被删除的节点，则将其next返回给上一个节点的next，否则，就返回本节点给上一个节点的next，保持不变。