LeetCode：203.移除链表元素

1、方法1：直接使用原来的链表来进行删除操作

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;
    }
};

1.1 删除头节点的元素

while(head != NULL && head->value == target)

问题：为什么要判断头节点不为空呢?
因为接下来要取头结点的值，如果头节点是空那么就相当于操作空指针了。
问题：为什么是while而不是if
假设有一串链表包含5个节点，每个节点的value都是1，而target也是1，那么就相当于要做5次移除头节点的工作。如果是if的话，其实只会做一次。用while的话，就相当于直到满足第一个节点的值不等于target为止

1.2 从内存中释放旧节点
如果使用C，C++编程语言的话，需要手动释放内存。其他语言的代码就不需要手动释放内存，会自动释放。

ListNode* tmp = head;
delete tmp;

还要说明一下，就算使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。

1.3 删除非头结点元素
先定义一个临时指针cur = head

问题：为什么定义cur = head，而不直接使用head操作
答：因为最后要返回head头指针，这样其他人才能找到这个删除后的链表。如果不这么做，而是直接移动头指针，最后就找不到这个链表了。
所以在遍历链表的时候，都需要定义一个临时指针
问题：为什么定义cur = head，而不是等于head->next
答：单链表删除的操作，是通过找到被删除节点前一个结点，然后让他直接指向被删除结点下一个结点来实现的

1.4 理解链表的两句话
cur = cur->next;移动cur指针，让cur指针指向链表下一个结点
cur->next = cur->next->next;不移动cur指针，但是改变cur指针指向结点后面跟随的结点，修改结点指针域，让其指向下下个结点。

2、方法2：设置一个虚拟头结点在进行移除节点操作

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

定义一个结点，让这个结点指向链表的头节点
问题：为什么要再写head = dummyHead->next;
答：因为head指向的是链表第一个结点，这个结点可能已经被我们删掉了，而且我们没有改变head指针的指向。