在o（1）时间删除链表结点

现在的位置: 首页 > 综合 > 正文

在o（1）时间删除链表结点

2013年10月16日 ⁄ 综合 ⁄ 共 5615字 ⁄ 字号小中大 ⁄ 评论关闭

题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。

函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，更重要的是，还能考察我们对时间复杂度的理解。

在链表中删除一个结点，最常规的做法是从链表的头结点开始，顺序查找要删除的结点，找到之后再删除。由于需要顺序查找，时间复杂度自然就是O(n) 了。

我们之所以需要从头结点开始查找要删除的结点，是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点，由于我们已经得到实际删除的结点的前面一个结点，因此完全是可以实现的。当然，在删除之前，我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时，时间复杂度为O(1)。

上面的思路还有一个问题：如果删除的结点位于链表的尾部，没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺便遍历得到给定结点的前序结点，并完成删除操作。

最后需要注意的是，如果链表中只有一个结点，而我们又要删除链表的头结点，此时我们在删除结点后，还需要把链表的头结点设置为NULL。

需要全面的考虑到删除的结点位于链表的尾部及输入的链表只有一个结点的特殊情况。

这个时候时间复杂度是O(n)。那题目要求我们需要在O(1)时间完成删除操作，我们的算法是不是不符合要求？实际上，假设链表总共有n个结点，我们的算法在n-1总情况下时间复杂度是O(1)，只有当给定的结点处于链表末尾的时候，时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n，仍然为O(1)。

核心代码：

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
    if(!pListHead || !pToBeDeleted)
        return;

    // 要删除的结点不是尾结点
    if(pToBeDeleted->m_pNext != NULL)
    {
        ListNode* pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nValue = pNext->m_nValue;
        pToBeDeleted->m_pNext = pNext->m_pNext;
 
        delete pNext;
        pNext = 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 = NULL;
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

实现代码：

#include<iostream>
using namespace std;

typedef struct ListNode
{
    int m_nKey;
    struct ListNode *m_pNext;
}ListNode , *LinkList;

void InsertList(LinkList &L , int data) //头插入
{
    ListNode *p = new ListNode();
    p->m_nKey = data;
    if(NULL == L)
        p->m_pNext = NULL;
    else
        p->m_pNext = L;
    L = p;
}

void PrintList(LinkList L) //打印链表
{
    ListNode *p = L;
    while(p)
    {
        cout<<p->m_nKey<<" ";
        p = p->m_pNext;
    }
    cout<<endl;
}


void DeleteNode(LinkList &L , ListNode *pToBeDeleted)  //删除链表L中的pToBeDeleted结点
{
    if(!L || !pToBeDeleted)
        return;
    //要删除的结点不是尾结点
    if(pToBeDeleted->m_pNext != NULL)
    {
        ListNode *pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nKey = pNext->m_nKey;
        pToBeDeleted->m_pNext = pNext->m_pNext;

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

    }
}

void main()
{
    LinkList L = NULL;
    ListNode *p;
    int n;
    InsertList(L, 3);  
    InsertList(L, 7);  
    InsertList(L, 12);  
    InsertList(L, 56);  
    InsertList(L, 33);  
    InsertList(L, 78);  
    InsertList(L, 20);  
    InsertList(L, 89);  
  
    PrintList(L);  
    cout<<"请输入要删除的节点：";  
    cin>>n;  
  
    p=L;  
    while(p->m_nKey!=n && p)  
        p=p->m_pNext;  
  
    if(!p)  
    {  
        cout<<"不存在这样的节点！"<<endl;  
        return;  
    }  
    else  
        DeleteNode(L, p);  
  
    cout<<"删除后的链表：";  
    PrintList(L);  

}

参看《剑指offer》里的代码：

#include<stdio.h>
#include<stdlib.h>

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

void PrintList(ListNode* pHead)
{
    printf("PrintList starts.\n");
    
    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        printf("%d\t", pNode->m_nValue);
        pNode = pNode->m_pNext;
    }

    printf("\nPrintList ends.\n");
}

void PrintListNode(ListNode* pNode)
{ 
    if(pNode == NULL)
    {
        printf("The node is NULL\n");
    }
    else
    {
        printf("The key in node is %d.\n", pNode->m_nValue);
    }
}

ListNode* CreateListNode(int value)
{
    ListNode* pNode = new ListNode();
    pNode->m_nValue = value;
    pNode->m_pNext = NULL;

    return pNode;
}

void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
{
    if(pCurrent == NULL)
    {
        printf("Error to connect two nodes.\n");
        exit(1);
    }

    pCurrent->m_pNext = pNext;
}

void DestroyList(ListNode* pHead)
{
    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        pHead = pHead->m_pNext;
        delete pNode;
        pNode = pHead;
    }
}

//----------------------------------------------------------------

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
    if(!pListHead || !pToBeDeleted)
        return;

    // 要删除的结点不是尾结点
    if(pToBeDeleted->m_pNext != NULL)
    {
        ListNode* pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nValue = pNext->m_nValue;
        pToBeDeleted->m_pNext = pNext->m_pNext;
 
        delete pNext;
        pNext = 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 = NULL;
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

// ====================测试代码====================
void Test(ListNode* pListHead, ListNode* pNode)
{
    printf("The original list is: \n");
    PrintList(pListHead);

    printf("The node to be deleted is: \n");
    PrintListNode(pNode);

    DeleteNode(&pListHead, pNode);
    
    printf("The result list is: \n");
    PrintList(pListHead);
}

// 链表中有多个结点，删除中间的结点
void Test1()
{
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);

    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);

    Test(pNode1, pNode3);

    DestroyList(pNode1);
}

// 链表中有多个结点，删除尾结点
void Test2()
{
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);

    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);

    Test(pNode1, pNode5);

    DestroyList(pNode1);
}

// 链表中有多个结点，删除头结点
void Test3()
{
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);

    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);

    Test(pNode1, pNode1);

    DestroyList(pNode1);
}

// 链表中只有一个结点，删除头结点
void Test4()
{
    ListNode* pNode1 = CreateListNode(1);

    Test(pNode1, pNode1);
}

// 链表为空
void Test5()
{
    Test(NULL, NULL);
}

int main()
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();

    return 0;
}

测试用例：

功能测试（从有多个节点的链表的中间删除一个结点，从有多个结点的链表中删除头结点，从有多个节点的链表中删除尾结点，从只有一个机诶单的链表中删除唯一的结点）。
特殊输入测试（指向链表头结点指针的为NULL指针，指向要删除的结点为NULL指针）。

【上篇】读书笔记: Java用zip和gzip压缩数据流
【下篇】FlashFXP软件使用方法

作者: injure

该日志由 injure 于11年前发表在综合分类下，最后更新于 2013年10月16日.
转载请注明: 在o（1）时间删除链表结点 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

在o（1）时间删除链表结点

作者: injure

书签

最新文章New

本站推荐

返回首页