【IT笔试面试题整理】在O(1)时间删除链表节点

【试题描述】给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间删除该节点。

【试题来源】 未知

【试题分析】按照常规删除链表节点的方法没有办法在O(1)复杂度内完成,因此需要转换思路,将后面一个节点的内容复制过来,然后删除其后面的那个节点,以达到删除节点的目的。

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct ListNode
{
int value;
ListNode* next;
};

void deleteLinkNode(ListNode** pHeadNode, ListNode* pDeleteNode) {

if(pHeadNode == NULL || pDeleteNode == NULL) {
return ;
}

//删除节点在头部
if(pDeleteNode == *pHeadNode) {
delete pDeleteNode;
pDeleteNode = NULL;
*pHeadNode = NULL;
//删除节点在末尾
} else if(pDeleteNode->next == NULL) {
ListNode* pNode = *pHeadNode;
while(pNode->next != pDeleteNode) {
pNode = pNode->next;
}
pNode->next = NULL;
delete pDeleteNode;
pDeleteNode = NULL;
} else {
ListNode* pNode = pDeleteNode->next;

pDeleteNode->value = pNode->value;
pDeleteNode->next = pNode->next;

delete pNode;
pNode = NULL;
}
}
坚持原创技术分享,您的支持将鼓励我继续创作!