且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

O(1)时间内删除指定链表结点

更新时间:2022-06-18 03:10:35

题目

给定单链表头指针和一个结点指针,定义一个函数在O(1)时间内删除该结点。

O(1)时间内删除指定链表结点

分析

对于上图实例链表(a)删除指针p有两种方式

  • 思路1:(b)找到前一个指针pre,赋值pre->next = p->next,删掉p
  • 思路2:(c)目的是删除p,但是不删p,直接用p->next的值赋值给p,把p->next删除掉(好处:不用遍历找到p的前一个指针pre,O(1)时间内搞定)

于是,定位到思路2,但是思路2有两个特例:

  1. 删除的是尾指针,需要遍历找到前一个指针
  2. 整个链表就一个结点(属于删尾指针,但没法找到前面的指针,需要开小灶单独处理)

大体算法思路

O(1)时间内删除指定链表结点
待删指针不是尾指针:
      待删指针的值用待删指针的下一个指针的值覆盖
      删掉待删指针的下一个指针
待删指针是尾指针:
      待删指针同时是头指针:
            删掉头指针
     待删指针不是头指针
            找到待删指针的前一个指针
            删掉待删指针,前一个指针的next赋值为空
O(1)时间内删除指定链表结点

参考代码

O(1)时间内删除指定链表结点
bool deleteNode(ListNode *&head, ListNode *p)
{
    if(!p || !head)
        return false;
    if(p->m_pNext != NULL)   //不是尾指针
    {
        ListNode *del = p->m_pNext;
        p->m_nValue = del->m_nValue;
        p->m_pNext = del->m_pNext;
        delete del;
        del = NULL;
    }
    else if(head == p)       //是尾指针,同时只有一个结点
    {
        delete p;
        head = NULL;
    }
    else                     //是尾指针,同时有多个结点
    {
        ListNode *tmp = NULL, *pre = head;
        while(pre->m_pNext != p)
        {
            pre = pre->m_pNext;
        }
        delete p;
        p = NULL;
        pre->m_pNext = NULL;
    }
    return true;
}
O(1)时间内删除指定链表结点

完整代码1

O(1)时间内删除指定链表结点 View Code

完整代码2

O(1)时间内删除指定链表结点 View Code

分析

删除非尾结点时间复杂读为O(1),删除尾结点的时间复杂读为O(n), 平均时间复杂度为[(n-1)*O(1) + O(N)] / N = O(1)

还有删除函数并不能处理待删结点就是该链表中的指针,因此需要人为调用时控制,如果得验证的话,那就没必要做这些处理了,直接O(N)

技术细节——传值操作

O(1)时间内删除指定链表结点
#include <iostream>
using namespace std;

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

void createList(ListNode *head)
{
    head = new(ListNode);
    head->m_nValue = 1;
    head->m_pNext = NULL;
}
void deleteList(ListNode *p)
{
    ListNode *next = NULL;
    while(p != NULL)
    {
        cout << p->m_nValue << endl;
        next = p->m_pNext;
        delete p;
        p = NULL;
        p = next;
    }
}

int main()
{
    ListNode *head = NULL;
    createList(head);
    cout << head << endl;
    deleteList(head);
}
    
O(1)时间内删除指定链表结点

主函数中的指针head为传值调用,传到函数并没有改变主函数中的值,图示

O(1)时间内删除指定链表结点

改进的措施就是引用传值,直接操纵原指针。





本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/p/3603564.html,如需转载请自行联系原作者