首页 > 代码库 > O(1)时间删除链表的已知结点

O(1)时间删除链表的已知结点

2024-07-07 14:41:00   225人阅读

这题并不需要从头结点遍历到已知结点，只需要知道已知结点，将改结点下一个结点赋值给它，再删除这个下一个结点就行，其中还需要考虑各种情况。

1）链表为空或者已知结点为空

2）链表只有一个结点，这个结点就是要删除的已知结点

3）要删除的已知结点在链表的末尾，此时就不能将下一个结点复制过去，我们就需要采用传统方法了。从头结点遍历找到该节点的上一个结点

#include "stdafx.h"
#include <iostream>
using namespace std;
typedef int Type;
typedef struct List
{
    Type data;
    List * next;
}; 

void deleteListNode(List **L, List * deleteNode)
{
    //容错性的检查 
    if(!L||!deleteNode)
        return;
    //只有一个结点
    if(*L=deleteNode)
    {
        delete deleteNode;
        deleteNode=NULL;
        *L=NULL;    //注意它的设置方式
    }
    //删除的结点不是尾点
    else if(deleteNode->next!=NULL)
    {
        List *nextNode=new List ;
        nextNode=deleteNode->next;
        //将nextNode的数据赋值到node
        deleteNode->data=http://www.mamicode.com/nextNode->data;
        deleteNode->next=nextNode->next;
        delete nextNode; 
        nextNode=NULL;       //在删除结点后，还需要把链表的头结点设置为NULL,防止悬垂指针
    }
    //删除的结点是尾点,此时主要要把指向它的指针为NULL
    else
    {
        List *pNode=*L;      //当输入是**L,我们就当*L去使用它，也就是*L等价于L
        while(pNode->next!=deleteNode)
            pNode=pNode->next;
        pNode->next=NULL;
        delete deleteNode;
        deleteNode=NULL;
    }
}

时间复杂度分析：

当不是尾结点，显然复杂度为O(1)，当是尾结点，复杂度为O(N)。所以总得时间复杂度是（(n-1)O(1)+O(n)）/n 结果还是O(1)


联系
我们