面试题13:在O(1)时间删除链表结点
2024-08-27 03:55:52
题目:给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点。
链表结点与函数的定义如下:
struct ListNode
{
int val;
ListNode* next;
};
分析:如下图所示,假设要删除的结点为p结点,若直接删除p结点,则必须知道p的上一个结点,而查找p的上一个结点的时间复杂度为O(N)。可以交换p和p的下一个结点q的数据,然后直接删除q,这样便保证了时间复杂度为O(1)。需要注意的是p为尾结点的情况。这时只能顺序遍历链表并完成删除操作。
ListNode * deleteNode( ListNode* head, ListNode* toBeDeleted)
{
if (head==NULL || toBeDeleted == NULL)
return head;
if (toBeDeleted->next!=NULL)
{//删除的结点不是尾结点
ListNode* q = toBeDeleted->next;
toBeDeleted->val = q->val;
toBeDeleted->next = q->next;
delete q;
q = NULL;
}
else
{
if (toBeDeleted == head)
{//删除的结点既是头结点也是尾结点
delete toBeDeleted;
head = NULL;
toBeDeleted = NULL;
}
else
{//删除的结点是尾结点不是头结点
ListNode* p = head;
while (p->next!=toBeDeleted)
p = p->next;
p->next = NULL;
delete toBeDeleted;
toBeDeleted = NULL;
}
}
return head;
}
PS:上述代码存在一个问题,因为它基于一个假设:要删除的结点的确在链表中。我们需要O(N)的时间才能判断链表中是否包含某一结点。
受到O(1)时间的限制,我们不得不把确保结点在链表中的责任推给了函数的调用者。在面试的时候,可以和面试官讨论这个假设,以便让面试官觉得我们考虑问题非常全面。
最新文章
- 数据库 之MySQL 简单教程
- H5摇一摇遇到的问题
- DataStage
- EXTJS 4.2 资料 控件之checkboxgroup的用法(静态数据)
- 1010 [HNOI2008]玩具装箱toy
- NFinal 揭秘之控制器
- hdu 2503 a/b + c/d
- Struts2环境的搭建
- 二叉查找树(Binary Search Tree)
- Redis、Memcache、MongoDb的优缺点
- python requests库的简单使用
- Snort规则大探秘
- python笔记05:条件、循环和其它语句
- GreenPlum学习笔记:create table创建表
- Java中日期类型和mysql中日期类型进行整合
- [12] 扇形体(Fan)图形的生成算法
- 转:system.Security.Cryptography C# 加密和解密
- Java基础随笔
- BZOJ4290 传送门
- Python操作列表