首页 > 代码库 > O(1)时间删除链表节点

O(1)时间删除链表节点

问题描述:给定单相链表的头指针和一个节点指针,定义一个函数在O(1)时间删除该节点。

这个比较简单,做不做解释,直接看参考代码,不过有一点就是要注意,还是要看删除的节点类型,不能保证总是O(1)时间

 

参考代码:

void DeleteNode(ListNode** pHead,ListNode *pTobeDelete)
{
    if ((pHead == NULL) || (*pHead == NULL) || (pTobeDelete == NULL))
    {
        return;
    }
 
    //删除的是链表中间的节点
    if (pTobeDelete->m_pNext != NULL)
    {
        ListNode *pNode = pTobeDelete->m_pNext;
        pTobeDelete->m_nValue = http://www.mamicode.com/pNode->m_nValue;
        pTobeDelete->m_pNext = pNode->m_pNext;
        delete pNode;
        pNode = NULL;
    }
    else
    {//只有一个节点
        if (pTobeDelete == *pHead)
        {
            delete *pHead;
            pHead = NULL;
            pTobeDelete = NULL;
        }
        else
        {//删除的尾节点
            ListNode *pNode = *pHead;
            while (pNode->m_pNext != pTobeDelete)
            {
                pNode = pNode->m_pNext;
            }
            pNode->m_pNext = NULL;
            delete pTobeDelete;
            pTobeDelete = NULL;
        }
    }
}

O(1)时间删除链表节点