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

移除链表元素

题目传送门

思路一:遍历链表

定义一个指针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;
}