O(1)的时间里面删除链表中的节点

O(1)的时间里面删除链表中的节点

关键考察O(1)时间内。如果我们有头节点了。根据遍历可以拿到当前节点的上一个节点，但是时间复杂度为O(n)

注意几个问题

• 边界条件的控制。传入的头指针和要删除的指针是否为0

• 删除不是尾指针。当然链接也不是空

• 删除的是头指针也是尾指针

• 删除的是尾指针

我们通过将一个节点的元素内容拷贝到当前的元素，然后删除下一个节点的元素，完成当前元素的删除。

  struct ListNode {


     int m_nValue;
     ListNode*m_pNext;
 };

 // O(1)时间内删除表中的节点

 void deleteNode(ListNode**pListHead,ListNode*pToBeDelete){
if (!pListHead || !pToBeDelete) {
    return;
}
//如果删除的不是尾节点
if (pToBeDelete->m_pNext !=nullptr) {
    ListNode*pNext = pToBeDelete->m_pNext;
    pToBeDelete->m_nValue = pNext->m_nValue;
    pToBeDelete->m_pNext = pNext->m_pNext;
}else if (*pListHead == pToBeDelete){ //如果只有头节点。也就是只要尾节点
    delete pToBeDelete;
    pToBeDelete = nullptr;
    *pListHead = nullptr;
}else{  //删除尾节点。
    ListNode*listNode= *pListHead;
    while (listNode->m_pNext != pToBeDelete) {
        listNode = listNode->m_pNext;
    }
    
    listNode->m_pNext = nullptr;

    delete pToBeDelete;
    //很注意野指针异常的问题
    pToBeDelete = nullptr;
}
}