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

struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
};

//方法1：常规法，顺序查找要被删除的节点，时间复杂度为O(n)
void DeleteNode_1(ListNode** pListHead, ListNode* pToBeDeleted)
{
    if (pListHead == nullptr || *pListHead == nullptr)
        return;

    //若被删除的是首元节点，则将头指针指向第二个节点，删除首元节点
    if ((*pListHead)->m_pNext == pToBeDeleted)
    {
        pToBeDeleted = (*pListHead)->m_pNext;
        (*pListHead)->m_pNext = pToBeDeleted->m_pNext;
    }
    //若删除的是中间节点，则遍历链表至被删除节点的前驱
    else
    {
        ListNode* p = *pListHead;
        while (p->m_pNext!=pToBeDeleted&&p->m_pNext!=nullptr)
        {
            p = p->m_pNext;
        }
        pToBeDeleted = p->m_pNext;
        p->m_pNext = pToBeDeleted->m_pNext;
    }

    //判断要删除的节点是否非空，即是否真的存在这个要删除的节点
    if (pToBeDeleted != nullptr)
    {
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
    }
}

/*
方法2:特殊方法，不用顺序查找被删除的节点的前一个节点，而是只利用其后继节点,
用后继节点的值覆盖本该删除的那个节点，然后删除后继节点。时间复杂度为O(1)
*/
void DeleteNode_2(ListNode** pListHead, ListNode* pToBeDeleted)
{
    if (pListHead == nullptr || *pListHead == nullptr)
        return;
    //若该节点不为尾节点，有后继节点
    if (pToBeDeleted->m_pNext != nullptr)
    {
        pToBeDeleted->m_nValue = pToBeDeleted->m_pNext->m_nValue;
        pToBeDeleted = pToBeDeleted->m_pNext;
    }

    //若该节点为尾结点，无后继节点,则需顺序查找尾结点的前驱结点。
    else
    {
        ListNode* p = *pListHead;
        while (p->m_pNext!=pToBeDeleted&& p->m_pNext!=nullptr)
        {
            p = p->m_pNext;
        }
        pToBeDeleted = p->m_pNext;
        p->m_pNext = pToBeDeleted->m_pNext;
    }

    if (pToBeDeleted != nullptr)
    {
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
    }
}