用尾插的思想实现移除链表中的元素

目录

一、介绍尾插

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（遍历节点）三个指针

其思想是：将单个链表中符合要求的节点放到两个链表中分析，但需要在原来的链表中实现