《手撕链表题系列-1》删除链表中等于给定值 val 的所有节点

用户9645905

发布于 2022-11-30 11:41:32

3380

发布于 2022-11-30 11:41:32

文章被收录于专栏：Linux学习~

前言

本系列主要讲解链表的经典题

注：划重点！！必考~

删除链表中等于给定值 val 的所有节点

力扣链接：203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点

示例：

提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
解题思路：

这里我们选择使用尾插法，遍历链表把不是val的节点给尾插到一个新的链表上
这里对于在第一次尾插时（作为头节点）的特殊情况，我们选择创建带哨兵卫的头节点

注：创建带哨兵卫的头节点，在结束时记得释放（规范性）

参考代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    //写一个哨兵卫头节点
    struct ListNode*phead=malloc(sizeof(struct ListNode));
    phead->next=NULL;
    //创建两个当前寻址指针
    struct ListNode*cur1=head;
    struct ListNode*cur2=phead;
    while(cur1)//当cur1为NULL，则遍历链表完毕
    {
        if(cur1->val!=val)//不为删除值则接在有哨兵卫的链表后
        {
            cur2->next=cur1;
            //cur2指在链表尾端
            cur2=cur2->next;
        }
        //找到下一个地址
        cur1=cur1->next;
    }
    //遍历完将尾端置空
    cur2->next=NULL;
    //保存哨兵后一个地址
    struct ListNode*plist=phead->next;
    //释放哨兵
    free(phead);
    return plist;
}