DS-单链表：删除指定元素值x的结点

一、定义单链表结构

• 代码：

typedef int linkType;	       ///< 定义链表结点数据域数据类型

/// @brief  链表结点定义
typedef struct t_linkNode
{
    struct t_linkNode* pnext;  ///< 结点指针域
    linkType data;             ///< 结点数据域
}myLNode;

/// @brief 链表结构定义
typedef struct t_linkList
{
    myLNode* phead;   //< 链表头结点指针
}myLinkList;

二、删除单链表中元素值等于x的第一个结点

1、思路

• 代码：

/// @brief 删除链表中元素值为x的第一个结点
/// @param plist 链表指针
/// @param x 待删元素
/// @return 返回是否删除成功的标志
/// @retval ERROR(0)：链表不存在，不可操作
/// @retval FALSE(0)：找不到x元素结点,删除操作失败
status xxx_removeX(myLinkList* plist, linkType x)
{
    if (plist == NULL)
    {
        return ERROR;
    }
    return xxx_removeX_(plist->phead, x);
}
status xxx_removeX_(myLNode* phead, linkType x)
{
    if (phead == NULL || phead->pnext == NULL)
    {
        return ERROR;
    }
    myLNode* p = phead->pnext;
    myLNode* pre = phead;
    while (p != NULL && x != p->data)
    {
        pre = p;
        p = p->pnext;
    }
    /// 若p==NULL，说明遍历完链表仍未找到x结点，跳出循环
    if (p == NULL)
    {
        return FALSE;
    }
    pre->pnext = p->pnext;
    p->pnext = NULL;
    free(p);
    p = NULL;
    return OK;
}

三、删除元素值等于x的所有结点

1、思路一

• 代码

/// @brief 方法1：删除链表中所有元素值为x的结点
/// @param plist 链表指针
/// @param x 待删元素
/// @return 返回被删元素个数
/// @retval 0：删除失败
/// @retval 正整数：成功删除的结点个数
status xxx_remove_allX(myLinkList* plist, linkType x)
{
    if (plist == NULL)
    {
        return ERROR;
    }
    return xxx_remove_allX_2_(plist->phead, x);
}
status xxx_remove_allX_(myLNode* phead, linkType x)
{
    if (phead == NULL || phead->pnext == NULL)
    {
        return ERROR;
    }
    int i = 0;
    myLNode* p = phead->pnext;
    myLNode* pre = phead;
    while (p != NULL)
    {
        /// x!=p->data，则继续遍历链表
        if (x != p->data)
        {
            pre = p;
            p = p->pnext;
            continue;
        }
        /// 若x==p->data，则删除该结点p
        pre->pnext = p->pnext;
        p->pnext = NULL;
        free(p);
        p = pre->pnext;
        ++i;    ///< 记录被删结点个数
    }
    return i;
}

2、思路二

• 代码

/// @brief 方法2：遍历链表,找到第1个值为x的结点,px指向该结点,pre指向px前驱
/// 遍历px后继链表,只要遇到值不等于x的结点，就将该值拷贝至px所指向结点
/// 然后px,pre均向后移动一个结点。若遇到值为x的结点，则继续遍历剩下结点
/// 等到p遍历完px的后继链表后，整个链表就会被分为2部分。所有值不为x的值均已被
/// 拷贝至前部分结点，而px指向的结点及px之后所有结点均可以free掉
status xxx_remove_allX_1_(myLNode* phead, linkType x)
{
    if (phead == NULL || phead->pnext == NULL)
    {
        return ERROR;
    }
    myLNode* px = NULL;         ///< 记录链表中第一个值为x的结点
    myLNode* pre = phead;       ///< 记录px前驱
    myLNode* p = phead->pnext;  ///< 遍历指针
    /// 遍历链表，直接找到第一个值为x的结点，令px指向该结点,px指向其前驱
    while (p!= NULL)
    {
        if (p->data == x)
        {
            px = p;
            p = p->pnext;
            break;
       }
        pre = p;
        p = p->pnext;
    }
    /// 若px为空，说明整个链表没有值等于x的结点，函数退出
    if (px == NULL)
    {
        return FALSE;
    }
    /// 遍历px结点的后继链表，将不等于x的元素值逐个拷贝至最前边的px所指的结点
    /// 循环结束后，px指向结点及所有后继结点均可被free
    while (p != NULL)
    {
        if (p->data != x)
        {
            px->data = p->data;     ///< 非x元素值拷贝至px结点
            pre = px;   
            p = p->pnext;
            px = px->pnext;
            continue;
        }
        p = p->pnext;
    }
    /// pre为px前驱，同时也为新的结果链表的尾结点。将尾结点pnext域置空
    pre->pnext = NULL;
    /// 释放px及其后继结点
    while (px != NULL)
    {
        p = px->pnext;
        free(px);
        px = p;
    }
    return OK;
}

3、思路3

• 代码

/// @brief 方法3：是方法2的改进
status xxx_remove_allX_2_(myLNode* phead, linkType x)
{
    if (phead == NULL || phead->pnext == NULL)
    {
        return ERROR;
    }
    myLNode* px = phead;        ///< px假定指向值为x的结点
    myLNode* p = phead->pnext;  ///< 遍历指针
    while (p != NULL)
    {
        /// 只要值为x，该结点不用处理，继续遍历后续结点即可
        if (p->data == x)
        {
            p = p->pnext;
        }
        /// 若值不为x，将其与px所指结点交换元素值
        else
        {
            px = px->pnext;
            px->data = p->data;
            p = p->pnext;
        }
    }
    /// 将前部分值不为x的结点与后部分值为x的结点断开链接
    p = px->pnext;
    px->pnext = NULL;
    px = p;         ///< 令px指向待free结点
    while (p != NULL)
    {
        p = p->pnext;
        free(px);
        px = p;
    }
    return OK;
}