如何在o时间删除链表节点

发布网友 发布时间：2022-05-01 02:01

我来回答

共1个回答

热心网友 时间：2022-06-22 04:57

算法思路：

一般我们是从头节点开始遍历，知道找到要删除的节点的前面一个节点，但是时间复杂度为O(n)
改进思路：找到要删除的节点pDeleteNode的下一个节点pNext，把下一个节点的值（pNext->m_nValue）
赋给要删除的节点(PDeleteNode->m_nValue),再把要删除的节点指向下一个节点的下一个节点：（pDelete->m_pNext = pNext->m_pNext）
然后再把pNext节点删除，pNext = NULL；

代码：

[cpp] view plain copy print?
// DeleteNodeInList.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;

/*
算法思路：
一般我们是从头节点开始遍历，知道找到要删除的节点的前面一个节点，但是时间复杂度为O(n)
改进思路：找到要删除的节点pDeleteNode的下一个节点pNext，把下一个节点的值（pNext->m_nValue）
赋给要删除的节点(PDeleteNode->m_nValue),再把要删除的节点指向下一个节点的下一个节点：（pDelete->m_pNext = pNext->m_pNext）
然后再把pNext节点删除，pNext = NULL；

*/

struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
if (!pListHead || !pToBeDeleted)
{
return;
}
if (pToBeDeleted->m_pNext != NULL)//删除的节点不是尾巴节点
{
ListNode* p = pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue = p->m_nValue;
pToBeDeleted->m_pNext = p->m_pNext;

delete p;
p = NULL;
}
else if (*pListHead == pToBeDeleted)//链表只有一个节点，删除头节点也是尾巴节点
{
delete pToBeDeleted;
pToBeDeleted = NULL;
*pListHead = NULL;
}
else//链表中有多个节点，删除尾巴节点
{
ListNode* pNode = *pListHead;
while (pNode->m_pNext != pToBeDeleted)
{
pNode = pNode->m_pNext;
}
pNode->m_pNext = pToBeDeleted->m_pNext;
delete pToBeDeleted;
pToBeDeleted = NULL;
}

}

/*
分析： 对于n-1个非尾巴节点而言，我们可以在O(1)的时间把下一个节点的内存复制覆盖要删除的节点，并删除下一个节点；
对于尾巴节点而言，由于仍然需要顺序查找，时间复杂度是O(n).因此总的平均时间复杂度是[(n-1)*O(1)+O(n)]/n,因此平均时间
复杂度是O(1);

*/

int _tmain(int argc, _TCHAR* argv[])
{
return 0;
}

对于n-1个非尾巴节点而言，我们可以在O(1)的时间把下一个节点的内存复制覆盖要删除的节点，并删除下一个节点；

对于尾巴节点而言，由于仍然需要顺序查找，时间复杂度是O(n).因此总的平均时间复杂度是[(n-1)*O(1)+O(n)]/n,

因此平均时间复杂度是O(1);