经典面试题18 - 在O(1)时间删除链表节点

问题:
给定链表的头指针和一个节点指针,在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;
}

经典面试100题 - 持续更新中

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容