【Leetcode】单链表 ---移除链表元素(创建虚拟头节点)

移除链表元素

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

题目思路

题目思路：
①要考虑到，在给链表中，被删除的链表元素可能是中间或者尾结点，但也可能是头结点。
首先，可以直接想到的是，对头节点是要被删除元素进行单独讨论。
但是，我们可以寻求更高效率的更直接的办法，就是 创建一个 虚拟结点(dummy)，使得虚拟节点指向头节点。
②当我们要返回时，返回虚拟节点(dummy)的next即可。
③遍历，我们要定义一个指针去遍历整个链表，即定义cur指针即可(当前指针current)，让cur指针初始指向dummy这个虚拟结点即可。
④条件判断，我们直接根据cur所指的结点的下一个结点的值是否等于val来判断进行删除。
⑤若进行删除，则，使得 cur->next=cur->next->next;即可。
⑥若不进行删除，则 cur=cur->next;

图解

下面，我将根据自己的理解发出直观的图解。
假设，一个简单的链表：

这是很直接的逻辑图，即从图中，我们看到，头指针head指向了结点值为1的结点，结点值为1的结点指向了结点值为2的结点，结点值为2的结点指向了结点值为3的结点……结点值为6的结点指向了不指向任何数据的指针。

为了加深理解，我们根据逻辑图画出其物理图：

物理图与逻辑图最根本的区别是物理图里没有逻辑图中的形象的箭头，这里是其本质的地址间的联系。
head指向结点值为1的结点即为 head中存放的是结点值为1的结点的地址。结点值为1的结点指向结点值为2的结点，其本质是，结点值为1的结点中的next域存放的是结点值为2的结点的地址……

创建虚拟头结点

//使用malloc函数在堆上开辟一个虚拟头节点
struct ListNode* dummy=(struct ListNode*)malloc(sizeof(struct ListNode))
1
2

在函数内部创建变量 dummy，其变量位置在栈上。
malloc函数在堆上开辟 struct ListNode这个结构体大小 的内存空间，并返回这块空间的地址。我们让dummy这个变量来管理堆上的这块内存。

之后，为了能够让我们创建的这个虚拟节点和我们原来的链表“线性连接”，我们给我们创建的这个虚拟头节点的next域赋值。

dummpy->next=head;
1

然后，我们就可以将我们创建的头节点和原来我们的链表“连接成线”了。

删除操作

利用cur指针进行遍历，循环的条件是

while(cur->next!=NULL)
{
   if (cur->next->val==val)
   {
       cur->next=cur->next->net;
   }
   else
   {
       cur=cur->next;
   }
}

1
2
3
4
5
6
7
8
9
10
11
12

(这里对于初学者来说很容易出错！)
这里简单说明一下 while(cur->next)!=NULL 和while(cur!=NULL)的区别。

我们可以看到如果是下面这种情况，cur指针依次访问，……访问到结点值为6的结点，然后指针移动，访问其后的空指针，然后不符合条件，不进入循环，（指针最后只在了最后的位置。）
问题主要出在了，当我们访问结点为6的结点时，不能访问cur->next->val,即不能访问NULL的val域，这样是非法访问了。

举个例子，若我们要删除的是结点值为3的结点：
即

那么更改cur->next:

如果cur指针所指向的结点的值不等于val的话，那么使val指针移动即可。

代码

 struct ListNode {
      int val;
      struct ListNode *next;
 };

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode *p=head;struct ListNode *q=NULL;

    //创建虚拟头节点
    struct ListNode *dummy=(struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next=head;
    struct ListNode *cur=dummy;
    while(cur->next!=NULL)
    {
        if(cur->next->val==val)
        {
            cur->next=cur->next->next;
        }
        else{
        cur=cur->next;}
    }
    return dummy->next;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24