关于单链表指定结点的前插操作O(n)时间复杂度的c语言代码

Question

（c语言）单链表中指定结点的前插操作
我知道有种时间复杂度最优的是O(1)
它的代码如下

bool InsertPriorNode_better(LNode* p,int e)
{
    if(p==NULL)
        return false;
    LNode* s=(LNode*)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->next=p->next;
    p->next=s;
    p->next->data=p->data;
    p->data=e;
    return true;
}

我想知道时间复杂度为O(n)的代码该如何实现

bool InsertPriorNode(LinkList L,LNode* p,int e)

函数声明为以上，思路是循环找到指定代码的前驱结点，然后插入
其中

typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode,*LinkList;

即LinkList L相当于LNode*,命名不同是为了增强可读性
代码ok马上采纳！谢谢！

Answer 1

这么写，供参考：

bool InsertPriorNode(LinkList L,LNode* p,int e)
{
    if (!L || !p)
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode)),* pL = L;
    if (!s)
        return false;
    s->data = e;
    s->next = NULL;
    if (L == p){
        s->next=p->next;
        p->next=s;
        p->next->data=p->data;
        p->data=e;
        return true;
    }
    while (pL && pL->next != p) pL = pL->next;
    s->next=pL->next;
    pL->next=s;
    return true;
}