LeetCode:203. 移除链表元素

目录

前言

题目

思路

问题1

问题2

问题3 

力扣代码实现

总结:


前言

小伙们大家好!今天小编为大家带俩一篇力扣上有关删除链表元素的题目:移除链表元素。

题目如下:

题目

LeetCode:203. 移除链表元素_第1张图片

如上图所示,题目中要求我们删除单链表中等于 val 的节点,然后返回头指针。那么我们发现,其实这个删除就与单链表中的指定位置删除节点差不多。

思路

那么分析完题目之后,其实我们发现,这里还是需要分为两种情况去分析的,首先就是头节点就是我们要删除的节点,其次就是其他任意节点。

问题1

首先,我们需要有两个指针,一个指针 cur 用来每次与 val 进行比较,另一个指针 prev 用来记录 cur 的前面一个位置。

然后当 cur 位置的值等于 val 时,需要用 prev 记住 cur 的下一个位置,然后当释放了 cur 了之后,再将该位置赋给 cur,保持两个指针的距离不变,然后一直到 cur 为空,也即链表为空,此时的链表就是去掉指定元素之后的链表。

问题2

因为删除的时候涉及到头节点的问题,所以需要分两种情况去实现。

首先,如果是头节点的话,我们需要用到单链表的头删,该删除和其他删除的方式略有不同。因为是头节点,所以删除了之后, head 指针需要指向第二个节点,正是因为 head 发生了变化,所以这是一种单独出现的情况。

其次,如果是非头节点的话,就是普通的删除了,就需要两个一前一后的指针去记录位置了。

问题3 

最后一个问题,如果不是要删除的元素,那么我们只需要先让 prev 指针移动到 cur 当前在的位置,然后再让 cur 往后移动一位即可。

力扣代码实现

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*cur=head;
    struct ListNode*prev=NULL;
    while(cur)
    {
        if(cur->val==val)
        {
            //头结点
            //涉及到头指针head
            if(cur==head)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            //非头结点
            else
            {
                prev->next=cur->next;
                free(cur);
                cur=prev->next;
            }
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }  
    return head;    
}

总结:

好的,那么对于本文,其实小编写的很简单,因为对于单链表的头删,尾删以及指定位置的删除,都是有一定的规则的,只要我们可以通过画图的方式将其认识清楚,那么本文的删除方式就是一个单链表删除的引申例子。

tips:如有小伙伴对于单链表的基本功能还不太了解,可以先移步小编的单链表文章哦,里面有更为详细的有关于单链表删除的讲解哦!

LeetCode:203. 移除链表元素_第2张图片

你可能感兴趣的