当前位置：首页 > ds >正文

【数据结构与算法】203.移除链表元素（LeetCode）图文详解

ds 2025/7/12 6:15:32

移除链表元素

题目传送门

在这里插入图片描述

思路一:遍历链表

定义一个指针prev遍历整个数组如果他下一个节点的val值为val，就移除这个节点,让prev的next指针指向被删除的下一个节点,然后prev后移,直到prev的next指针为空

在这里插入图片描述

按照这个思路，有以下代码

struct ListNode* prev;
while(prev!=NULL)
{if(prev->next->val=val){struct ListNode* del=prev->next;prev->next=del->next;free(del);//释放内存时，必须用原指针 }else{prev=prev->next;}
}

我们再来看特殊的情况

链表为空时

直接返回空指针

if(head==NULL)
{return NULL;
}

头节点的val值为被删除的元素时

while(head!=NULL&&head->val==val)
{struct ListNode*del=head;head=head->next;free(del);}

完整代码如下

struct ListNode* removeElements(struct ListNode* head, int val) {while(head!=NULL&&head->val==val) {struct ListNode*del=head;head=head->next;free(del);}if(head==NULL){return NULL;}struct ListNode*prev = head;while(prev->next!=NULL){if(prev->next->val==val){struct ListNode* del=prev->next;prev->next=prev->next->next;free(del);}else{prev=prev->next;}}return head;    
}

思路二:创建新的链表

本质：定义一个指针pcur 让他去遍历原链表如果pcur->val不为val,就把他尾插到新的链表中

struct ListNode* removeElements(struct ListNode* head, int val){//创建新的头节点 尾节点struct ListNode* NewHead,*NewTail;NewHead=NULL;NewTail=NULL;struct ListNode*pcur=head;//遍历原链表while(pcur){//找值不为val的节点,尾插到新链表中if(pcur->val!=val){//链表为空（第一次插入）if(NewHead==NULL){NewHead = NewTail = pcur;}//链表不为空else{NewTail->next=pcur;//pcur插入到NewTail后 成为新的尾节点NewTail=NewTail->next;}}pcur=pcur->next;if(NewTail!=NULL)NewTail->next=NULL;//一定要置为空，不然像示例一中最后的6 也会输出 因为5对应的next指针指向的是6这个节点}        return NewHead;
}