C语言/数据结构——每日一题（移除链表元素）

ops/2024/9/25 9:14:25/

一.前言

今天在leetcode刷到了一道关于单链表的题。想着和大家分享一下。废话不多说，让我们开始今天的知识分享吧。

二.正文

1.1题目要求

1.2思路剖析

我们可以创建一个新的单链表，然后通过对原单链表的遍历，将数据不等于val的节点移到新的单链表上。循环往复，新单链表上的元素就是全部不等于val的元素了。此时return 我们的新单链表的头节点，就完成了这道题目。

我们可以让新单链表的头节点设为，ListNode* phead，尾节点为ListNode* ptail。（ListNode*为单链表数据类型）

phead用于我们后面返回该链表的头节点（因此头节点不可随意设置）

ptail用于我们在给新单链表尾部插入旧单链表的时候，方便通过尾节点ptail链接我们后面插入的元素。值得注意的是(假设后面插入的元素是pafter)：当我们通过ptail->next链接尾部插入的元素pafter后，不要忘了让ptail=ptail->next。让ptail指向pafter代表的地址（事实上就是使pafter代表的元素为尾节点）

1.3代码实现

以下就是在leetcode环境下运行的源代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;struct ListNode* removeElements(struct ListNode* head, int val)
{ListNode* pcur = head;ListNode* phead;ListNode* ptail;// ListNode* phead,*ptail;phead=ptail=NULL;//ListNode* pcur=head;if (head==NULL)return head;else{while (pcur){if (pcur->val!= val){if (phead==NULL){phead = ptail = pcur;}else{ptail->next = pcur;ptail = ptail->next;}}pcur = pcur->next;}}if(ptail!=NULL)ptail->next = NULL;
return phead;
}

这里面有个易踩的坑就是这里ptail->next=NULL；这一步是必须的。否则当你通过示例一的时候你会发现输出的结果是1，2，3，4，5，6。

你可能会疑惑为什么前面的6被除掉了，后面的6没有被除掉呢？

这是因为当尾节点ptail指向代表元素5的时候，ptail->next实际指向的还是元素6的地址。因此在最后我们需要将ptail->next=NULL。才能正确返回1，2，3，4，5。