[数据结构与算法]Leecode 203-移除链表元素

题目描述

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

代码一

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


struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode *h,*L,*p;
    //如果链表为空或者只有一个元素且该元素为要删除的值
    if(head==NULL||(head->val==val&&head->next==NULL))
        return NULL;

    //设置两个指针，分别指向链表当前结点和下一个结点
    //也顺便保证链表头结点不丢失，保证链表删除元素后依然完整
    h=head; 
    L=head->next;
    //利用循环将链表中除了第一个结点之外的满足删除条件的结点删除
    while(L!=NULL)
    {
        if(L->val==val) //当前结点满足删除条件
        {
            p=L;
            L=L->next; //L指向其下一个结点
            h->next=L;  //h指向L
            free(p); //释放所删除结点的内存空间
        }
        else
        {
            L=L->next;
            h=h->next;
        }
    }
    if(head->val==val)         //判断第一个结点是否需要删除
        head=head->next;
    return head;
}

代码二（添加一个虚拟头结点）

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


struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode *h,*H,*L,*p;
    //如果链表为空或者只有一个元素且该元素为要删除的值
    if(head==NULL)
        return NULL;
    //添加一个虚拟头结点
    h=(struct ListNode *)malloc(sizeof(struct ListNode));
    h->val=-1;
    h->next=head;

    H=h;
    L=h->next;

    while(L!=NULL)
    {
        if(L->val==val)
        {
            p=L;    //临时保存被删结点地址以便释放
            L=L->next; //L指向被删结点的下一个结点
            H->next=p->next;    //改变被删结点前驱的指针域
            free(p);    //释放删除结点的空间
        }
        else
        {
            L=L->next;
            H=H->next;
        }
    }
    return h->next;
}

单链表如果有头结点的话会方便对首元结点的处理，该链表无首元结点，因此构造一个新的结点让其指针域指向该链表作为该链表的头结点，从而方便当链表首元结点需要删除时对其的处理

代码三（使用递归，官方给的解答之一）

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


struct ListNode* removeElements(struct ListNode* head, int val){
    if(head==NULL)
        return head;
    
    head->next = removeElements(head->next,val);
    return head->val == val ? head->next : head;
}

这种方法运行时间快了，但是内存消耗比较大。