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

今日写题04work

article 2025/2/21 5:25:40

题目：移除链表元素

两种实现思路

思路一

使用双指针，prev，cur快慢指针解决。当cur不等于val，两个指针跳过。当等于val时，要考虑两种情况，一种是pos删，一种是头删除。

pos删除就是正常情况，但头删是一种特殊情况，比如第一个数据就是等于val。所以，我们在这里分类处理。

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

思路二

尾插到新链表，如果不等于val，尾插到新链表。如果等于val,那就头删。末尾记得把tail的next置空，否则如果最后一个数据要删除的话，那tail的next就成了野指针。还有两种特殊情况，空链表和全等于val。

空链表

tail等于空指针，如果末尾在使用就是空指针引用。

全等于val

这时全部头删，没有一个结点尾插。那tail还是空指针，末尾使用就是空指针引用。

这两种情况都是空指针引用错误。所以，我们可以在末尾加一个if语句，判断tail是否为空。

如果为空，就不执行。如果不为空，那就执行。

最后记得return的是新的头指针，newHead。


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