删除链表中等于给定值 val 的所有结点（三种方法深入解析）

又见面啦，接下来的链表相关Oj题目我会根据我自己的理解来给大家讲解，包括解析和代码，希望你可以对链表有更加深入的理解！！

---

题目：

先上链接：

OJ题目

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

方法一：迭代 

 想法：遍历链表，找到这个val前面一个结点，让这个结点指向val的next

 注意：在寻找为给定值的结点时，需要先判断结点是否为空结点

if (head != nullptr && head->val == val) {
	head = head->next;
}

 

 结果如下：

struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head != nullptr && head->val == val) {
	head = head->next;
}
    if(NULL==head){
        return head;
    }
    struct ListNode*pre=head;
    while(pre->next!=NULL)
    {
        if(pre->next->val==val)
        {
            pre->next=pre->next->next;
        }
        else 
        {
            pre=pre->next;
        }
    }
    return head;
    
}

方法二：双指针

设置两个指针，值为head

 

cur右移判断他的val 是否为要删除的值，如果不是pre右移

 

 

直到cur->val==val;这个时候的pre就是这个需要删除结点的前结点，让pre->next=cur->next， 遍历完整个链表就可以了

 看一下代码

struct ListNode* removeElements(struct ListNode* head, int val){
    while (NULL != head && head->val == val) {
        head = head->next;
    }
    
    struct ListNode* cur = head;
    struct ListNode* pre = head;
    while (cur != NULL) {
        if (cur->val == val) {
            pre->next = cur->next;
        } else {
            pre = cur;
        }
        cur = cur->next;
    }
    return head;
}

虚拟头结点

可以通过在头结点前增加虚拟头结点，这样子头结点就变成了普通结点

看代码

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

---

每天进步一点点，积少成多，大家一起努力！