203. 移除链表元素

思路一：直接删除法（迭代）

1.从头结点开始向后遍历，找到等于val的结点；

2.假设cur->val = val，那么要让cur的前一个结点prev的next指针指向cur的下一个结点，即prev->next = cur->next。

要注意的是当头结点的值等于val时（head->val = val），因为头节点没有前一个结点，所以可以通过直接改变头节点使其指向头节点的下一个结点（head = head->next）。

代码如下：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //当头节点为val时，将头结点向后移动
        while(head && head->val == val) 
        {
            ListNode* tmp = head;//新建一个结点方便删除结点
            head = head->next;
            delete tmp;
        } 
        //判断链表是否为空
        if(head == nullptr)
        {
            return nullptr;
        }
        ListNode* cur = head;//记录当前结点
        ListNode* prev = head;//记录上一个结点
        while(cur)
        {
            if(cur->val == val)//当结点值和val相等时删除
            {
                prev->next = cur->next;
                delete cur;//删除该节点
                cur = prev->next;
            }
            else{ //不等于时cur直接向后移动
                prev = cur;
                cur = cur->next;
            }
        }
        return head;
    }
};

时间复杂度：O(N)

空间复杂度：O(1)

思路二：虚拟头结点（哨兵位）

上面的思路需要判断当头节点的值是否等于val，并且需要将头节点后移，我们可以通过设置一个虚拟头结点，让其链表本来的头结点链接在虚拟头节点的后面，这样头结点就成普通结点了，就无需再单独进行处理了。

注意返回的时候返回的是虚拟头节点的下一个结点，并非返回虚拟头节点。

代码如下：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* newhead = new ListNode(0);//申请一个虚拟头节点
        newhead->next = head;//将head链接到虚拟头节点后面
        if(newhead->next != nullptr) //当head不为空时，进入
        {
            ListNode* cur = head;
            ListNode* prev = newhead;
            while(cur)
            {
                if(cur->val == val)
                {
                    prev->next = cur->next;
                    delete cur;
                    cur = prev->next;
                }
                else
                {
                    prev = cur;
                    cur = cur->next;
                }
            }
        }
        head = newhead->next; //返回的是虚拟头节点的下一个结点
        delete newhead;
        return head;
    }
};

时间复杂度：O(N)

空间复杂度：O(1)