在O(1)时间删除链表结点

发表于 | 分类于

##QUESTION
给定单项链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该节点。

##O(n)解法
O(n)解法就是常规的删除链表结点的做法。从链表的头结点开始，顺序遍历查找要删除的结点，并在链表中删除该结点。这种思路由于要顺序查找，时间复杂度自然就是O(n)了。

之所以要从头开始查找，是因为我们需要得到将被删除的结点的前面一个结点。在单向链表中，结点中没有指向前一个结点的指针，所以只好从链表的头结点开始顺序查找。

##O(1)解法
那是不是一定要得到被删除结点的前一个节点呢？答案是否定的。我们可以这样来删除一个结点，例子如下，别删除的结点为i，i的下一个结点为j：

  • 把j结点的内容复制到i结点，覆盖i结点的内容
  • 将i结点的next指向j结点的next
  • 删除j结点

这里我们删除的虽然是j结点，但是得到的效果却是删除了i结点。

还有一个问题，当我们删除的结点是尾结点时，尾结点的next是NULL，上述解法就不再适用，我们还是要顺序遍历后删除尾结点。

代码如下：

typedef struct Node
{
    int data;
    struct Node *next;
}*node;

/*在O(1)时间删除结点*/
void DeleteNode(node &pListHead, node pToBeDeleted)
{
    if(!pListHead || !pToBeDeleted)
        return;

    // 要删除的结点不是尾结点
    if(pToBeDeleted->next!= NULL)
    {
        node pNext = pToBeDeleted->next;
        pToBeDeleted->data= pNext->data;
        pToBeDeleted->next = pNext->next;

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

        pNode->next = NULL;
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

我们分析一下这个思路的时间复杂度。对于n-1个非尾结点而言，我们可以在O(1)时把下一个结点的内存复制覆盖要删除的结点，并删除下一个结点；对于尾结点而言，由于仍需要顺序查找，时间复杂度为O(n).因此总的时间复杂度为[(n-1)*O(1)+O(n)]/n,结果仍然是O(1),符合要求。