文章目录
题目
题目链接：203. 移除链表元素
思路1–无哨兵结点的迭代
要删除链表中的元素：首先要找到该元素的结点；
定义一个cur ：表示指向要删的元素结点；定义一个prev:表示要删的元素的前面的结点；
先让 prev的next指向 cur的next;再释放cur;同时，cur 要继续迭代往前走，找是否还有要删除的元素，此时让cur指向prev的next即可；
如果链表为空，直接返回空指针；
实现代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* cur = head;
struct ListNode* perv = NULL;
while(cur)
{
//遍历到要删除的结点
if(cur->val == val)
{
//在if条件成立的前提下单独处理：假设要删除的节点是头结点
if(cur == head)
{
//修改头指针的指向，不在指向头结点，改为指向cur->next
head = cur->next;
free(cur);
cur = head;
}
else
{
//要删除结点的前一个结点指向要删除结点的后一个结点
perv->next = cur->next;
//释放删除的结点
free(cur);
//同时当前结点指向被删除结点的下一个结点
cur = perv->next;
}
}
else //若干当前结点与val不相等
{
//在else成立的前提下，perv往前移动
perv = cur;
cur = cur->next;
}
}
//当退出循环表示cur到尾结点 或者 直接没有进入循环而是直接是空链表
return head;
}
思路2–有哨兵结点的迭代
相比于没有哨兵结点的迭代，**有哨兵结点的迭代有很好的处理头删的方式！**即头删不会与其他位置的删除造成不一样的逻辑处理.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode* cur = head;
struct ListNode* pre = dummyHead;
while (cur != NULL)
{
if (cur->val == val)
{
pre->next = cur->next;
free(cur);
cur = pre->next;
}
else
{
pre = cur;
cur =cur->next;
}
}
return dummyHead->next;
}
思路2–递归
由于链表有天然的递归结构，所以很容易想到可以递归解决问题！
要删除val，返回头结点；那么我们就递归删除head->next;即可，得到一个新的结点newNode;
这个结点就是删除完后的结点；用head->next链接newNode；
然后再判断head头结点是否要删除的值：不是就直接返回head，是的就直接返回head->next(即newNode结点)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
ListNode* removeElements(struct ListNode* head, int val) {
if(!head ) return NULL;
//要删除链表中的结点：也就是删除head->next的结点
struct ListNode* newNode = removeElements(head->next,val);
//头结点连接删好后的链表
head->next = newNode;
//判断头节点的值是否和要删的val相同
return head->val == val ? head->next : head;
}