数据结构：删除单链表中p节点，时间复杂度O(1)

categories:

• 数据结构

题目背景

在plist中删除p节点，时间复杂度要求O(1)

算法

因为时间复杂度为O(1)，所以常规思路遍历链表是不行的。删除节点，其实是把该节点数据域清除，已知了p节点，那么可以知道它的next节点，所以可以把p节点的下一个节点的数据域赋值给p节点数据域，再让p节点的next指向p->next->next，就实现了p节点数据域的清除，也就间接删除了p节点。
如果p是最后一个节点，则只好遍历链表，复杂度O(n)
只有p是最后一个节点时间复杂度才是O(n),平均时间复杂度(O(1)*(n-1) + O(n))/n = O(1)，所以该算法时间复杂度仍为O(1)

C代码

bool DeleteP(Linklist plist, Linklist p)//在plist中删除p节点，O(1)
{
    assert(plist != NULL);
    assert(p != NULL);
    if (plist == NULL || p == NULL)    
        return false;
    if (p->next != NULL)//p不是最后一个节点
    {
        //把p->next->data的值赋值给p->data,再让p->next指向下下个节点
        p->data = p->next->data;
        p->next = p->next->next;
        free(p->next);
        return true;
    }
    else//p是最后一个节点
    {
        LinkList tmp;
        for (; tmp->next->next != NULL;)
        {
            tmp = tmp->next;
        }
        tmp->next = NULL;
        free(tmp->next->next);
        return true;
    }
}