【题目】
给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:
structListNode
{
int value;
struct ListNode*next;
};
函数的声明如下:
voidDeleteNode(ListNode* head,ListNode* node);
【思路】
这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解。
在链表中删除一个结点,最常规的做法是从链表的头结点开始,顺序查找要删除的结点,找到之后再删除。由于需要顺序查找,时间复杂度自然就是O(n) 了。
我们之所以需要从头结点开始查找要删除的结点,是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点,由于我们已经得到实际删除的结点的前面一个结点,因此完全是可以实现的。当然,在删除之前,我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时,时间复杂度为O(1)。
上面的思路还有一个问题:如果删除的结点位于链表的尾部,没有下一个结点,怎么办?我们仍然从链表的头结点开始,顺便遍历得到给定结点的前序结点,并完成删除操作。这个时候时间复杂度是O(n)。
那题目要求我们需要在O(1)时间完成删除操作,我们的算法是不是不符合要求?实际上,假设链表总共有n个结点,我们的算法在n-1总情况下时间复杂度是O(1),只有当给定的结点处于链表末尾的时候,时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n,仍然为O(1)。
基于前面的分析,我们不难写出下面的代码。
/*********************************
* 日期:2014-10-29
* 作者:SJF0115
* 题目: 给定链表的头指针和一个结点指针,在O(1)时间删除该结点
* 来源:经典面试题
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
//O(1)时间 删除链表中的节点
void DeleteNode(ListNode** head,ListNode* node){
if(head == NULL || node == NULL){
return;
}
ListNode* p = node->next;
// 删除的不是末尾节点 O(1)
if(p != NULL){
//删除p节点
node->next = p->next;
// 节点p复制到node节点
node->next = p->next;
node->val = p->val;
delete p;
p = NULL;
}
// 删除的是末尾节点 O(n)
else{
ListNode* pre = *head;
// 末尾节点
while(pre->next != node){
pre = pre->next;
}
//删除node节点
pre->next = NULL;
delete node;
node = NULL;
}
}
int main() {
ListNode* node1 = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(3);
ListNode* node4 = new ListNode(4);
ListNode* node5 = new ListNode(5);
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
//无头结点链表
DeleteNode(&node1,node2);
while(node1 != NULL){
printf("%d ",node1->val);
node1 = node1->next;
}
return 0;
}
何海涛:
值得注意的是,为了让代码看起来简洁一些,上面的代码基于两个假设:(1)给定的结点的确在链表中;(2)给定的要删除的结点不是链表的头结点。不考虑第一个假设对代码的鲁棒性是有影响的。至于第二个假设,当整个列表只有一个结点时,代码会有问题。但这个假设不算很过分,因为在有些链表的实现中,会创建一个虚拟的链表头,并不是一个实际的链表结点。这样要删除的结点就不可能是链表的头结点了。当然,在面试中,我们可以把这些假设和面试官交流。这样,面试官还是会觉得我们考虑问题很周到的。
分享到:
相关推荐
在O(1)时间删除链表结点.md
要求控制台显示如下内容,然后根据前方数字进行相应操作 1、创建一条含整数结点的无序链表 2、链表结点的输出 3、链表结点的升序排序 4、分别计算链表中奇数和偶数结点之和并输出 5、释放链表 0、退出
在O(1)时间删除链表结点给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点,链表结点与函数的定义如下:// 要删除的结点不是尾结点//
定义、实现并测试一个双向链表结点类DNode。...编写主程序:输入不少于3组x、y整数,分别利用左侧和右侧插入结点函数组织数据为双向链表,测试输出链表中每个结点的左侧和右侧相邻节点内容,测试对左右侧结点的删除。
链表结点插入算法
java面试 java面试_leetcode面试题解之第19题删除链表的倒数第N个结点
C实现删除链表中指定结点,可以指定结点的值
删除链表结点PPT学习教案.pptx
/*链表的结点删除部分略*/}程序运行结果为: 333 gong 222 chen 111 wang3. 以下结点node定义了一个学生的信息,函数del
python_leetcode面试题解之第19题删除链表的倒数第N个结点
有详细的讲解和代码,而且代码不是伪码,方便大家学习。
每敲一次代码都会有新的收获,基本功不扎实啥也干不了。单向链表的插入,删除,创建,遍历是数据结构的基本操作。里边的算法值得学习。下面我们就来学习一下单向链表结点的逐个删除的方法。
链表结点的删除.cpp
1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,多和面试官沟通,然后开始做一些整体的设计和规划。不要急于提交,自己测试几个用例避免错误...
微软面试题,输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。适合新手入门结构清晰易懂
个人总结的, C语言删除链表单个结点。适合新手
删除链表中倒数第N个结点后,返回结果链表的首结点
用C++简单实现无头结点的建表,插入,删除操作
面试题 04.03. 特定深度节点链表解题思路层次遍历+链表。复杂度分析时间复杂度:O(N)空间复杂度:O(N)代码实现i++ { // 遍历每一层。
这个程序涉及单向链表的“创建”、“结点删除”、“查找”、“筛选”、“结点插入”、“结点排序”几项内容,并且已在必要的地方写了注释,方便大家阅读程序。本人编此程序花了不少心思,向大家要的分多了点,但绝对...