链表01--移除链表元素

203 Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

示例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

输出：[]

思路

然后，对于C、CPP，要注意从内存中删除不要的节点，清理内存之后：

上面的移除操作，就是让节点next指针直接指向下下一个节点。

那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表的中第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？

这里就涉及如下链表操作的两种方式：

• 直接使用原来的链表来进行删除操作。
• 设置一个虚拟头结点在进行删除操作。

直接使用原来的链表来进行移除

如果要移除非头节点，需要next指针指向下一个节点，但是，当需要移除头节点时，因为没有更前面的节点，所以操作发生了变化！

移除头节点的操作，只需要head后移一位；

但是会导致代码逻辑更复杂！

设置一个虚拟头结点在进行删除操作

设置一个虚拟头结点，原链表的所有节点就都可以按照统一的方式进行移除了。

来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。

最后，return头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点。

Solution

使用原来的链表

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

设置虚拟头节点

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

再来个C语言版本比较一下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    typedef struct ListNode ListNode;
    ListNode *shead;
    shead = (ListNode *)malloc(sizeof(ListNode));
    shead->next = head;
    ListNode *cur = shead;
    while(cur->next != NULL){
        if (cur->next->val == val){
            ListNode *tmp = cur->next;
            cur->next = cur->next->next;
            free(tmp);
        }
        else{
            cur = cur->next;
        }
    }
    head = shead->next;
    free(shead);
    return head;
}