用尾插的思想实现移除链表中的元素
目录
一、介绍尾插
1.链表为空
2.链表不为空
二、题目介绍
三、思路
四、代码
五、代码解析
1.
2.
3.
4.
5.
6.
六、注意点
1.
2.
一、介绍尾插
整体思路为
1.链表为空
void SLPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuyLTNode(x); //每次尾插都要建立新的节点 //BuyLTNode(x)该函数用于得到新节点if (*pphead == NULL) //没有节点，先赋值。 赋值不需要用到 tail ！！！{*pphead = newnode;}}需要注意的是：第一次尾插，只需要插入数据计科，并不需要建立tail指针、进行后移等操作
2.链表不为空
else //此时才会用到 tail ！
{SLTNode* tail = *pphead;while (tail->next != NULL) //找尾{tail = tail->next;}tail->next = newnode;
}此时需要：1.找尾 2.插入数据
二、题目介绍
203. 移除链表元素
已解答
简单
相关标签
相关企业
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 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 输出：[]
三、思路
新建一个newhead指针和 tail 指针，将不是val的节点尾插到tail中。
四、代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* tail = NULL, *newhead = NULL; //*newhead 不是newheadstruct ListNode* cur = head;while(cur){if(cur->val != val){if(newhead == NULL) //没有节点的时候，只需要插进去即可，并不需要指针后移！{newhead = tail = cur; //tail从newcode开始}else //应该在此处将整个链表串接{tail->next = cur; //tail本质是指向cur的空间tail = tail->next;}cur = cur->next; //为了防止tail和cur指向同一块空间。cur先往后走tail->next = NULL; //tail的下一个节点置空。}else{struct ListNode* del = cur; //要删除的元素暂存在del中cur = cur->next;free(del); }}return newhead;}五、代码解析
1.
struct ListNode* tail = NULL, *newhead = NULL; //*newhead 不是newhead
struct ListNode* cur = head;
新建指针，利用cur去遍历节点。
2.
if(newhead == NULL) //没有节点的时候，只需要插进去即可，并不需要指针后移！
{
newhead = tail = cur; //tail从newcode开始
}
类比尾插没有节点的时候
3.
else //应该在此处将整个链表串接
{
tail->next = cur; //本质是让tail指向cur的空间。tail只是一个指针！
tail = tail->next;
}
类比有节点的尾插
4.
cur = cur->next;
tail->next = NULL; //为了防止出现野指针问题（heap-use-after-free 释放后的堆使用）
在while循环的第一个条件中，应用该语句链接整个链表，作为循环的控制语句。
5.
else
{
struct ListNode* del = cur; //要删除的元素暂存在del中
cur = cur->next;
free(del);
}
当元素val等于的时候，需要借助一个del指针，删除需要删除的元素。
6.
return newhead; 返回新的节点
六、注意点
需要注意的是：
1.
cur = cur->next;
tail->next = NULL;
①作为循环的控制语句，可以写在 子if 之外
②应该先让cur后移，再让tail的next指针置空。 若先置空tail->next，那么此时tail与cur是指向同一节点，此时cur的next也将置空！
③若链表的尾val也需要删除，此时free（tail）之后，仍存在一个指向不明的野指针！
④若子if 子else句同时用到的语句，且不存在先后问题（先后问题指一般无删除）
此时可以将共同的语句封装在外部。
⑤尾插是让tail不断赶上cur，让cur始终领先于或平齐于tail！tail是新链表的尾部。
2.
尾插的思想常用在对链表节点的重新排序。
需要用到 tail newhead cur（遍历节点）三个指针
其思想是：将单个链表中符合要求的节点放到两个链表中分析，但需要在原来的链表中实现