leetcode:203. 移除链表元素(有哨兵位的单链表和无哨兵位的单链表)

简介: leetcode:203. 移除链表元素(有哨兵位的单链表和无哨兵位的单链表)

一、题目

函数原型:

struct ListNode* removeElements(struct ListNode* head, int val)

二、思路

本题有两种思路:

思路1

遍历单链表,如果遇到值为val的结点,则将该结点删除。

注意:当删除结点时,如果出现头结点为要删除的结点,那么prev->next就是对NULL进行解引用,所以这种情况需要先删除头结点,下一个结点作为新的头结点。

思路2

设置一个新的链表,遍历原有链表,如果遇到值不为val的结点,则将该结点尾插到新链表上,最终返回新链表。

思路2有两种实现方法,一种是带哨兵位的链表,另一种是不带哨兵位的链表

三、代码实现

思路1代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    if(head==NULL)
        return NULL;
    while(head&&head->val==val)//先删除符合删除条件的头结点
    {
        struct ListNode *tmp=head;
        head=head->next;
        free(tmp);
    }
    struct ListNode *prev=NULL;//定义前一指针,便于删除结点
    struct ListNode *cur=head;//定义遍历指针
    while(cur)
    {
        if(cur->val==val)//结点值等于val,删除结点
        {
            prev->next=cur->next;
            free(cur);
            cur=prev->next;
        }
        else//结点值不等于val,跳过结点
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

思路2代码(不带哨兵位)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode *cur=head;//遍历指针
    struct ListNode *newhead=NULL;//新的头结点
    struct ListNode *tail=newhead;//初始时尾指针指向新的头结点
    while(cur)//开始遍历原链表
    {
        if(cur->val!=val)//原链表结点值不等于val
        {
            if(tail==NULL)//初始时新链表为空,需要将要插入的结点作为新的头结点
            {
                newhead=tail=cur;
            }
            else//新链表不为空,进行尾插
            {
                tail->next=cur;
                tail=cur;
            }
            cur=cur->next;
        }
        else//销毁原链表中不需要的结点
        {
            struct ListNode *tmp=cur;
            cur=cur->next;
            free(tmp);
        }
        if(tail)//关键点,尾结点的指针域指向空
            tail->next=NULL;
    }
    return newhead;
}

思路2代码(带哨兵位)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode *newhead=NULL;
    struct ListNode *tail=NULL;
    //哨兵位
    newhead=(struct ListNode *)malloc(sizeof(struct ListNode));
    tail=newhead;//初始时,尾指针指向哨兵位
    struct ListNode *cur=head;//遍历指针
    while(cur)//开始遍历原链表
    {
        if(cur->val!=val)//有哨兵位,直接进行尾插,无需判断头结点是否为空
        {
            tail->next=cur;
            tail=cur;
            cur=cur->next;
        }
        else//销毁原链表中不需要的结点
        {
            struct ListNode *tmp=cur;
            cur=cur->next;
            free(tmp);
        }
    }
    tail->next=NULL;//关键点,新链表尾结点的指针域指向空
    //销毁哨兵位
    struct ListNode *tmp=newhead;
    newhead=newhead->next;
    free(tmp);
    return newhead;//返回新链表的头结点
}


目录
相关文章
|
1月前
|
存储
【单链表】数据结构单链表的实现
【单链表】数据结构单链表的实现
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
1月前
|
存储
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
141 38
|
1天前
|
算法
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
9 3
|
5天前
|
算法
【力扣】169. 多数元素
【力扣】169. 多数元素
|
5天前
【力扣】21. 合并两个有序链表
【力扣】21. 合并两个有序链表
|
17天前
|
缓存 算法 搜索推荐
【数据结构】链表(单链表与双链表实现+原理+源码)
【数据结构】链表(单链表与双链表实现+原理+源码)
|
1月前
|
存储 JavaScript
leetcode82. 删除排序链表中的重复元素 II
leetcode82. 删除排序链表中的重复元素 II
22 0
|
1月前
leetcode83. 删除排序链表中的重复元素
leetcode83. 删除排序链表中的重复元素
10 0
|
23天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
20 2