问题:
给定链表的头指针和一个节点指针,在O(1)时间删除该节点。
解答:
主要思想是「狸猫换太子」,用下一个节点数据覆盖要删除的节点,然后删除下一个节点。
代码如下:
//O(1)时间删除链表节点,从无头单链表中删除节点。
void deleteRandomNode(Node *cur)
{
assert(cur != NULL);
assert(cur->next != NULL); //不能是尾节点, 尾节点行不通。
Node* pNext = cur->next;
cur->data = pNext->data;
cur->next = pNext->next;
delete pNext;
}