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

前言

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

注：划重点！！必考~

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

力扣链接：203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点

• 示例：

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

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

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

• 参考代码：

代码语言：javascript复制

/**
 * 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;
}

• 结果：

编程算法 node.js

0 人点赞