【LeetCode 06】203.移除链表元素-阿里云开发者社区

【LeetCode 06】203.移除链表元素

2024-10-14 8

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【LeetCode 06】203.移除链表元素

一、题意

题目中给出了结点定义：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;//数据域
 *     struct ListNode *next;//指针域
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    
    
}

二、思考过程

链表的删除和数组删除不一样；数组是内存是连续的存储空间，没有删除这个说法，只是元素之间的覆盖而已，而链表删除是修改指针即可。如下图：

链表元素的删除、移除主要有两种方式：

直接使用原来的链表进行删除
需要单独写逻辑删除头结点
设置虚拟头结点进行删除
对头结点的删除可以统一操作

2.1直接使用原来的链表进行删除

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
   //删除头节点
    while(head!=NULL&&head->val==val){
        ListNode *tmp=head;
        head=head->next;
        free(tmp);
    }
    
    //删除非头节点
    ListNode *cur=head;
    while(cur!=NULL&&cur->next!=NULL){
        if(cur->next->val==val){
            ListNode *tmp=cur->next;
            cur->next=cur->next->next;
            free(tmp);
        }else{
            cur=cur->next;
        }
    }
    return head;
  }
}

2.2设置一个虚拟节点再执行删除操作

设置一个虚拟头节点，这样原来的链表的所有节点都可以按照统一的方式删除了。

step:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 
  * typedef struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * }ListNode;添加即可取消【1】
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    typedef struct ListNode ListNode;//【1】
    ListNode *shead;
    shead=(ListNode*)malloc(sizeof(ListNode));
    shead->next=head;
    ListNode *cur=shead;
    while(cur->next!=NULL){
        if(cur->next->val==val){
            ListNode *tmp=cur->next;
            cur->next=cur->next->next;//关键
            free(tmp);
        }else{
            cur=cur->next;
        }
    }
    head=shead->next;
    free(shead);
    return head;
}