剑指Offer面试题：12.在O(1)时间删除链表结点 - 推酷
剑指Offer面试题：12.在O(1)时间删除链表结点
一、题目：在O(1)时间删除链表结点
题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
原文采用的是C/C++，这里采用C#，节点定义如下：
public class Node&T&
public T Item { get; set; }
public Node&T& Next { get; set; }
public Node()
public Node(T item)
this.Item =
要实现的DeleteNode方法定义如下：
public static void DeleteNode(Node&int& headNode, Node&int& deleteNode)
二、解题思路
2.1 常规思路
在单向链表中删除一个结点，最常规的做法无疑是从链表的头结点开始，顺序遍历查找要删除的结点，并在链表中删除该结点。这种思路由于需要顺序查找，时间复杂度自然就是 O(n) 。
2.2 正确思路
是不是一定需要得到被删除的结点的前一个结点呢？答案是否定的。
我们可以很方便地得到要删除的结点的一下结点。因此，我们
可以把下一个结点的内容复制到需要删除的结点上覆盖原有的内容，再把下一个结点删除，就相当于把当前需要删除的结点删除了
但是，还有两个特殊情况需要进行考虑：
（1）如果要删除的结点位于链表的尾部，那么它就没有下一个结点：
此时我们仍然从链表的头结点开始，顺序遍历得到该结点的前序结点，并完成删除操作，这仍然属于O(n)时间的操作。
（2）如果链表中只有一个结点，而我们又要删除链表的头结点（也是尾结点）：
此时我们在删除结点之后，还需要把链表的头结点设置为NULL。
最后，通过综合最坏情况（尾节点需要顺序查找，1次）和最好情况（n-1次），因此平均时间复杂度为：
需要注意的是：
受到O(1)时间的限制，我们不得不把确保结点在链表中的责任推给了函数DeleteNode的调用者
三、解决问题
3.1 代码实现
public static void DeleteNode(Node&int& headNode, Node&int& deleteNode)
if (headNode == null || deleteNode == null)
if (deleteNode.Next != null) // 链表有多个节点，要删除的不是尾节点:O(1)时间
Node&int& tempNode = deleteNode.N
deleteNode.Item = tempNode.I
deleteNode.Next = tempNode.N
tempNode = null;
else if (headNode == deleteNode) // 链表只有一个结点，删除头结点（也是尾结点）:O(1)时间
deleteNode = null;
headNode = null;
else // 链表有多个节点，要删除的是尾节点:O(n)时间
Node&int& tempNode = headN
while(tempNode.Next != deleteNode)
tempNode = tempNode.N
tempNode.Next = null;
deleteNode = null;
3.2 单元测试
（1）封装返回结果
该方法作为单元测试的对比方法，主要用来对比实际值与期望值是否一致：
public static string GetPrintNodes(Node&int& headNode)
if (headNode == null)
return string.E
StringBuilder sbNodes = new StringBuilder();
while(headNode != null)
sbNodes.Append(headNode.Item);
headNode = headNode.N
return sbNodes.ToString();
（2）测试用例
// 链表中有多个结点，删除中间的结点
[TestMethod]
public void DeleteNodeTest1()
Node&int& head1 = new Node&int&(1);
Node&int& head2 = new Node&int&(2);
Node&int& head3 = new Node&int&(3);
Node&int& head4 = new Node&int&(4);
Node&int& head5 = new Node&int&(5);
head1.Next = head2;
head2.Next = head3;
head3.Next = head4;
head4.Next = head5;
Program.DeleteNode(head1, head3);
Assert.AreEqual(Program.GetPrintNodes(head1),&1245&);
// 链表中有多个结点，删除尾结点
[TestMethod]
public void DeleteNodeTest2()
Node&int& head1 = new Node&int&(1);
Node&int& head2 = new Node&int&(2);
Node&int& head3 = new Node&int&(3);
Node&int& head4 = new Node&int&(4);
Node&int& head5 = new Node&int&(5);
head1.Next = head2;
head2.Next = head3;
head3.Next = head4;
head4.Next = head5;
Program.DeleteNode(head1, head5);
Assert.AreEqual(Program.GetPrintNodes(head1), &1234&);
// 链表中有多个结点，删除头结点
[TestMethod]
public void DeleteNodeTest3()
Node&int& head1 = new Node&int&(1);
Node&int& head2 = new Node&int&(2);
Node&int& head3 = new Node&int&(3);
Node&int& head4 = new Node&int&(4);
Node&int& head5 = new Node&int&(5);
head1.Next = head2;
head2.Next = head3;
head3.Next = head4;
head4.Next = head5;
Program.DeleteNode(head1, head1);
Assert.AreEqual(Program.GetPrintNodes(head1), &2345&);
// 链表中只有一个结点，删除头结点
[TestMethod]
public void DeleteNodeTest4()
Node&int& head1 = new Node&int&(1);
Program.DeleteNode(head1, head1);
head1 = null;
Assert.AreEqual(Program.GetPrintNodes(head1), &&);
// 链表为空
[TestMethod]
public void DeleteNodeTest5()
Program.DeleteNode(null, null);
Assert.AreEqual(Program.GetPrintNodes(null), &&);
测试通过结果：
（3）代码覆盖率
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致博客访问： 83178
博文数量： 53
博客积分： 2200
博客等级： 大尉
技术积分： 570
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
/*=============================================================
&&&&&&&&&&&&&&目的：动态链表的综合操作
&&&&&&&&&&&&&&&
&&&&&&&&&&&&&算法分析：1、构造第一个结构体作为头
&&&&&&&&&&&&&&&&&&&&&&&2、以P2和P1为游码在结构体移动
&&&&&&&&&&&&&&&&&&&&&&&3、 p1负责存储新创立的结构体，p2负责指向新创立的结构体
&&&&&&&&&&&&&&&&&&&&&&&4、creat函数返回链表的头
==============================================================
&&&&&&&&&&&&&&作者：最后的村长
&&&&&&&&&&&&&&时间：日
&&&&&&&&&&&&&&工具：DEV C++
&&&&&&&&&&&&&&version：1.0
==============================================================*/
#include <stdio.h>
#include <stdlib.h>
//#define NULL 0
#define LEN sizeof(struct student)
struct student
&&&&&&&long num;
&&&&&&&int score;
&&&&&&&struct student *next;
&&&&&&&};//学生结构体定义，包含两个数据:学号和成绩
&&&&&&&int n;//n为全局变量，实现链表中元素个数的统计
&&&&&&&struct student *create(void)//开辟动态链表函数
&&&&&&&&&&&&&&struct student *head;
&&&&&&&&&&&&&&struct student *p1,*p2;
&&&&&&&&&&&&&&n=0;
&&&&&&&&&&&&&&long int stu_id=1100;
&&&&&&&&&&&&&&p1=p2=(struct student *)malloc(LEN);//
&&&&&&&&&&&&&&p1->num=stu_id;
&&&&&&&&&&&&&&printf("请输入1个学生的成绩：\n");
&&&&&&&&&&&&&&scanf("%d",&(p1->score));//第一个学生结构体创立结束
&&&&&&&&&&&&&&head=NULL;
&&&&&&&&&&&&&&while(p1->score!=0)
&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&n=n+1;//统计链表中结构体元素的个数
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if(n==1)head=p1;//头指针赋值
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&else p2->next=p1;//前一个结构体的next指向下一个结构体
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//！注意上面语句的执行顺序
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&p2=p1;//p2移向下一个结构体
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&p1=(struct student *)malloc(LEN);//新开辟一个结构体内存单元
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&stu_id=stu_id+2;
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&p1->num=stu_id;//对新开辟的结构体内元素初始化
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&printf("请输入%d个学生的成绩：\n",n+1);
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&printf("成绩：");
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&scanf("%d",&(p1->score));
&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&p2->next=NULL;
&&&&&&&&&&&&&&return head;
&&&&&&&&&&&&&&}
/*=============================================================*/
void print(struct student *head)
&&&&&struct student *p;
&&&&&printf("\n一共是 %d个学生成绩如下 :\n",n);
&&&&&p=head;
&&&&&if(head!=NULL)
&&&&&&&&&&&&&&&&&&&printf("%ld,%d\n",p->num,p->score);
&&&&&&&&&&&&&&&&&&&p=p->next;
&&&&&&&&&&&&&&&&&&&}while(p!=NULL);
&/*=============================================================*/
&struct student*del(struct student *head,long int delnum)
&&&&&&&&struct student *p1,*p2;
&&&&&&&&p2=p1=head;
&&&&&&&&if(head->num==delnum)//如果要删除的学生是第一个的话
&&&&&&&&printf("删除的学生是第一个\n");
&&&&&&&&head=head->next;
&&&&&&&&n--;//学生总数减一
&&&&&&&&&&&&else//删除的学生不是第一个
&&&&&&&&&&&&{
&&&&&&&&&&&&&&while(p1->num!=delnum)//遍历链表寻找要删除的学生
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&p2=p1;
&&&&&&&&&&&&&&&&p1=p1->next;
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&if((p1->next==NULL)&&(p1->num!=delnum))//链表中无此要删除的学生
&&&&&&&&&&&&&&&&printf("此链表中无要删除的学生\n");
&&&&&&&&&&&&&&&&else if((p1->next==NULL)&&(p1->num==delnum))//要删除的学生是最后一个
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&p2->next=NULL;
&&&&&&&&&&&&&&&&&&&&n--;//学生总数减一
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&else if(p1->num==delnum)//要删除的学生是链表中的其中一个
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&p1=p1->next;
&&&&&&&&&&&&&&&&p2->next=p1;
&&&&&&&&&&&&&&&&n--;//学生总数减一
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&&&&&&&&&&&&return head;
&/*=============================================================*/
&struct student *insert(struct student *head,struct student *p0)
&&&&&&&&struct student *p1,*p2;
&&&&&&&&p2=p1=head;//p1和p2指向头指针
&&&&&&&&if((p0->num)<(head->num))//如果插入学生的学号小于第一个学生的学号
&&&&&&&&&&head=p0;
&&&&&&&&&&p0->next=p1;
&&&&&&&&&&}
&&&&&&&&&&else //如果插入学生的学号大于第一个学生的学号
&&&&&&&&&&{
&&&&&&&&&&&&&&&while((p0->num)>(p1->num))//遍历链表对学生的的学号进行对比
&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&p2=p1;
&&&&&&&&&&&&&&&&&p1=p1->next;
&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&printf("p1当前指向的学生的序号是：%ld,成绩是：%d,指向的下一个学生的地址是：%d\n\n",p1->num,p1->score,p1->next);
&&&&&&&&&&&&&&&&&if(p1->next==NULL)//链表遍历结束也没有找到比插入学生的学号大的
&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&p1->next=p0;
&&&&&&&&&&&&&&&&&p0->next=NULL;
&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&else if((p0->num)<=(p1->num))//
&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&p2->next=p0;
&&&&&&&&&&&&&&&&&p0->next=p1;
&&&&&&&&&&&&&&&&&}
&&&&&&&&&&}
&&&&&&&&&&n++;
&&&&&&&&&&return (head);
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
int main()
&&&&struct student *p,*head;
&&&&//======================创建并输出链表
&&&&head=create();//创建链表
&&&&print(head);//打印创建后的链表
&&&&for(int i=0;i<10;i++)
&&&&{printf("========");}
&&&&puts("\n");
&&&&//===========================删除一个学生
&&&&unsigned int delnum;//定义要删除的学生号
&&&&printf("请输入要删除的学生号：\n");
&&&&scanf("%u",&delnum);//输入要删除学生号
&&&&head=del(head,delnum);//删除学生号
&&&&printf("输出删除学号：%ld的学生后的链表\n",delnum);
&&&&print(head);//打印删除后的学生号
&&&&for(int i=0;i<10;i++)
&&&&{printf("========");}
&&&&puts("\n");
&&&&//=====================插入一个学生
&&&&struct student stu;
&&&&//初始化待插入的学生的学号和成绩
&&&&puts("请输入待插入学生的学号：");
&&&&scanf("%ld",&stu.num);
&&&&puts("请输入待插入学生的成绩：");
&&&&scanf("%d",&stu.score);
&&&&head=insert(head,&stu);
&&&&printf("输出插入学号：%ld，成绩：%d的学生后的链表\n",stu.num,stu.score);
&&&&print(head);
&&&&for(int i=0;i<10;i++)
&&&&{printf("========");}
&&&&puts("\n");
&&&&//===================
&&&&system("PAUSE");
&&&&return 0;
代码中的逻辑错误有时候代码编译通过之后的运行结果并不是自己想要的，这个时候就只能是按照自己的逻辑思路来认真核对和检查吗，没有其他的办法吗？？？？这说明代码注释的重要性，起码将来看代码不会一头雾水！！！！
阅读(5134) | 评论(0) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
编写一个C++程序,实现创建、输出链表,查找、插入、删除结点等功能：
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口求大神解答这道题，有关C++单链表问题，多谢啦 - 爱问知识人
(window.slotbydup=window.slotbydup || []).push({
id: '2491531',
container: s,
size: '150,90',
display: 'inlay-fix'
++单链表问题，多谢啦
点击 好评，祝福你 。
您的举报已经提交成功，我们将尽快处理，谢谢！
你好，全称应该是《阅读书单》推荐的各类书名，希望你利用课余时间看的。大概就是这样 例如。。。
1、《木兰诗》
2、《招魂》
3、《洛神赋》
大家还关注c++delete释放链表的节点问题，悲剧了。
[问题点数：40分，结帖人qhgongzi]
c++delete释放链表的节点问题，悲剧了。
[问题点数：40分，结帖人qhgongzi]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
本帖子已过去太久远了，不再提供回复功能。