问题描述:给定单相链表的头指针和一个节点指针,定义一个函数在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 = 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;
}
}
}