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 非NULL：查找成功
/// @retval 0地址值：查找失败
myLNode* xxx_findPre(myLinkList* plist, linkType x)
{
    if (plist == NULL)
    {
        return NULL;
    }
    return xxx_findPre_(plist->phead, x);
}
myLNode* xxx_findPre_( myLNode* phead, linkType x)
{
    if (phead == NULL || phead->pnext == NULL)
    {
        return NULL;
    }
    myLNode* p = phead->pnext;  ///< 记录待查x所在结点
    myLNode* pre = phead;       ///< 记录待查x所在结点的前驱结点
    while (p != NULL && p->data != x)
    {
        pre = p;
        p = p->pnext;
    }
    /// 若已经找到，则p不为空，若遍历完仍未找到，则p为空
    if (p == NULL)
    {
        pre = NULL;
    }
    return pre;
}